Slashdot Mirror

← Back to Stories (view on slashdot.org)

Wolfram Offers Prize For (2,3) Turing Machine

Posted by kdawson on from the universal-or-not dept.

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."

3 of 164 comments (clear)

  1. Re:Sounds like... by Anonymous Coward · · Score: 5, Interesting

    Wolfram has previously sued his own employees to keep them from publishing results, and there are many stories about him removing peoples' names from credits.

    Perhaps this is the only way he can now get creative people to work on problems like this.

  2. No Halting State by sugarmotor · · Score: 5, Interesting

    The description states that the machine has no halting-state.

    I couldn't make out what is to be interpreted as the result of a particular computation of this machine.

    Seems like a pretty important detail.

    Anyone know?

    Stephan

    --
    http://stephan.sugarmotor.org
  3. Arrow of time is reversed in CA by hajus · · Score: 5, Interesting

    The problem I have with CA being proposed as a model of a reality is that the arrow of time in CA seems to be backwards. In our reality, we know the past, but the future is uncertain. In cellular automata, the future can be predicted perfectly, but the states which were used to get to the current state are ambiguous. Large grids of such give the illusion of life (such as behaviour of predator/prey) but only a macroscopic scale even though time goes backward. But the arrow of time becomes very visible when the cells are focussed in on. If you decide to look at it in reverse time to satisfy the microscopic view, you don't get that feeling of life at the macroscopic scale.