Skip to content

Operations Research and Turing Machines

From slashdot.com:

An anonymous reader writes “Stephen Wolfram, creator of Mathematica and author of A New Kind of Science, is offering a prize of $25K to anyone who can prove or disprove his conjecture that a particular 2-state, 3-color Turing machine is universal. If true, it would be the simplest universal TM, and possibly the simplest universal computational system. The announcement comes on the 5-year anniversary of the publication of NKS, where among other things Wolfram introduced the current reigning TM champion — ‘rule 110,’ with 2 states and 5 colors.”

Operations research (particularly integer programming) seems relevant to this work (through things like the undecidability of integer quadratic programming). $25,000 anyone?

{ 1 } Trackback

  1. […] wrote previously about a competition Stephen Wolfram (of Mathematica fame) had to show that a particularly small […]