Wolfram's 2-state 3-symbol Turing machine

In his "A New Kind of Science", Stephen Wolfram found a universal 2-state 5-color Turing machine, and [http://www.wolframscience.com/nksonline/page-709 conjectured] that a particular 2-state 3-color Turing machine (hereinafter (2,3) Turing machine) might be universal as well.

On May 14, 2007, Wolfram announced a $25,000 prize [http://www.wolframscience.com/prizes/tm23/] to be won by the first person to prove or disprove the universality of the (2,3) Turing machine. According to Wolfram, the purpose of the prize was to encourage research to help answer foundational questions associated with the structure of what he calls the "computational universe".

Description

In each state, the machine reads the bit under the head and executes the instructions in the following table (where P"n" prints bit "n", "L" and "R" are left and right respectively, and A and B mean "switch to that state").

:

The (2,3) Turing machine:
*Has no halt state;
*Is trivially related to 23 other machines by interchange of states, colors and directions.

It is known that standard (2,2) machines cannot be universal as discussed briefly by Minsky (1967). Hence making the (2,3) Turing machine the smallest possible universal Turing machine.

The state of the head (up or down droplet) and the pattern of colour (orange, yellow and white) in a given row depends solely on the content of the row immediately above it.

Even though the machine has a head with only two states, and a tape that can hold only three colours (depending on the initial content of the tape), the machine's output can still be remarkably complex. [http://www.nature.com/news/2007/071024/full/news.2007.190.html]

Proof of universality

On 24 October 2007, it was announced that Alex Smith, a student in electronics and computing at the University of Birmingham (UK), proved that the (2,3) Turing machine is universal and thus won Wolfram's prize described above [http://blog.wired.com/wiredscience/2007/10/college-kid-pro.html] . The proof showed that the machine is equivalent to a variant of a tag system already known to be universal. Smith first constructed a sequence of rule systems showing that the (2,3) Turing machine is capable of arbitrary finite computations. He then employed a novel approach to extend that construction to unbounded computations. The proof proceeds in two stages. The first part emulates the finite evolution of any two-color cyclic tag system. The emulation is a composite of a series of emulations involving the indexed rule systems 'system 0' through 'system 5'. Each rule system emulates the next one in the sequence. Smith then showed that even though the initial condition of the (2,3) Turing machine is not repetitive, the construction of that initial condition is not universal. Hence the (2,3) Turing machine is universal.

Vaughan Pratt disputed the correctness of this proof in a public list of discussion [http://cs.nyu.edu/pipermail/fom/2007-October/012156.html] , noting that similar techniques would allow a linear bounded automaton to be universal, which would contradict a known non-universality result due to Noam Chomsky. In their reply to Pratt, Wolfram Research and Alex Smith rejected Pratt's claim. [cite web|url=http://cs.nyu.edu/pipermail/fom/2007-October/012149.html|title=Stephen Wolfram reply in the FOM list] [cite web|url=http://cs.nyu.edu/pipermail/fom/2007-October/012162.html|title=Todd Rowland reply to Vaughan Pratt in the FOM list] [cite web|url=http://cs.nyu.edu/pipermail/fom/2007-October/012164.html|title=Alex Smith reply to Vaughan Pratt in the FOM list] [cite web|url=http://cs.nyu.edu/pipermail/fom/2007-November/012227.html|title=Alex Smith further precision to Vaughan Pratt in the FOM list]

Wolfram claims that Smith's proof is another piece of evidence for Wolfram's general "Principle of Computational Equivalence" (PCE). [http://cs.nyu.edu/pipermail/fom/2007-October/012149.html] That principle states that if one sees behavior that is not obviously simple, the behavior will correspond to a computation that is in a sense "maximally sophisticated." [http://www.ddj.com/blog/portal/archives/2007/05/the_prize_and_u.html] Smith's proof has unleashed a debate on the precise operational conditions a Turing machine must satisfy in order for it to be candidate universal machine.

A universal (2,3) Turing machine has conceivable applications [http://technology.newscientist.com/article/dn12826-simplest-universal-computer-wins-student-25000.html] . For instance, a machine that small and simple can be embedded or constructed using a small number of particles or molecules. But the "compiler" Smith's algorithm implies does not produce compact or efficient code, at least for anything but the simplest cases. Hence the resulting code tends to be astronomically large and very inefficient. Whether there exist more efficient codings enabling the (2,3) Turing machine to compute more rapidly is an open question.

ee also

*Turing machine
*Universal Turing machine
*Turing machine examples
*Turing completeness
*Rule 110
*tag system
*automata theory
*finite state machine

Notes

References

*Wolfram, S (2002) " A New Kind of Science". Wolfram Media.
* Wolfram Research, Inc., " [http://www.wolfram.com/news/researchprize.html Prize Announced for Determining the Boundaries of Turing Machine Computation,] " Formal announcement that Alex Smith has won the prize.
*------, [http://www.wolframscience.com/prizes/tm23/ Wolfram 2,3 Turing Machine Research Prize.] Invitation to contestants.

Historical reading

*Marvin Minsky (1967) "Computation: Finite and Infinite Machines". Prentice Hall.
*Turing, A (1937) " [http://www.thocp.net/biographies/papers/turing_oncomputablenumbers_1936.pdf On Computable Numbers with an Application to the "Entscheidungsproblem",] " "Proceedings of the London Mathematical Society Series 2, 42": 230-265.
*------ (1938) "On Computable Numbers, with an Application to the "Entscheidungsproblem". A Correction," "Proceedings of the London Mathematical Society Series 2, 43": 544-546.

External links

*" [http://www.nature.com/news/2007/071024/full/news.2007.190.html Student snags maths prize,] " "Nature". Published online 24 October 2007.
*" [http://blog.wired.com/wiredscience/2007/10/college-kid-pro.html College Kid Proves That Wolfram's Turing Machine is the Simplest Universal Computer,] " "Wired Science". Published online 24 October 2007.
*" [http://technology.newscientist.com/article/dn12826-simplest-universal-computer-wins-student-25000.html Simplest 'universal computer' wins student $25,000,] " "New Scientist". Published online 24 October 2007.
*" [http://www.ddj.com/blog/portal/archives/2007/05/the_prize_and_u.html The Wolfram Prize and Universal Computation: It's Your Problem Now,] " "Dr. Dobbs Journal". Published online 22 October 2007.
*Minkel, J.R., " [http://www.sciam.com/article.cfm?chanID=sa003&articleID=D8F2082D-E7F2-99DF-36D4F98C7C2A7674&pageNumber=1&catID=1 A New Kind of Science Author Pays Brainy Undergrad $25,000 for Identifying Simplest Computer,] " "Scientific American", October 25, 2007.
* From Foundations of Mathematics discussion threads:
** [http://cs.nyu.edu/pipermail/fom/2007-October/012149.html Simple Turing machines, Universality, Encodings, etc.]
** [http://cs.nyu.edu/pipermail/fom/2007-October/012125.html Simplest universal Turing Machine.]
** [http://cs.nyu.edu/pipermail/fom/2007-October/012132.html Smallest universal machine.]
** [http://cs.nyu.edu/pipermail/fom/2007-October/012156.html Vaughan Pratt's claim that Smith's proof is invalid.]
** [http://cs.nyu.edu/pipermail/fom/2007-October/012149.html Wolfram's reply to Pratt in the same forum.]
** [http://cs.nyu.edu/pipermail/fom/2007-October/012162.html Reply to Pratt by Todd Rowland, one of the judges for the prize.]