wolframscience.com
We have the solution! Wolfram's 2,3 Turing Machine is universal. Congratulations Alex Smith.
Announced May 14th, 2007: 5th Anniversary of the Publication of A New Kind of Science
The Wolfram 2,3 Turing Machine Research Prize
$25,000 prize
Is this Turing machine universal, or not?

The machine has 2 states and 3 colors, and is 596440 in Wolfram's numbering scheme.
If it is universal then it is the smallest universal Turing machine that exists.




A universal Turing machine is powerful enough to emulate any standard computer.
The question is: how simple can the rules for a universal Turing machine be?

Since the 1960s it has been known that there is a universal 7,4 machine. In A New Kind of Science, Stephen Wolfram found a universal 2,5 machine, and suggested that the particular 2,3 machine that is the subject of this prize might be universal.

The prize is for determining whether or not the 2,3 machine is in fact universal.

What is a Turing Machine? »  |  Notable Universal Turing Machines »


INTERACTIVE DEMONSTRATIONS »        Printable Poster »        NKS|Online »

 


© 2011 Wolfram Institute | Contact