Wolfram's 2-state 3-symbol Turing machine

In his book A New Kind of Science, Stephen Wolfram described a universal 2-state 5-color Turing machine, and conjectured that a particular 2-state 3-symbol Turing machine (hereinafter (2,3) Turing machine) might be universal as well.[1]

On May 14, 2007, Wolfram announced a $25,000 prize to be won by the first person to prove or disprove the universality of the (2,3) Turing machine.[2] On 24 October 2007, it was announced that the prize had been won by Alex Smith, a student in electronics and computing at the University of Birmingham, for his proof that it was universal, though the proof was initially disputed.

Description

The following table indicates the actions to be performed by the Turing machine depending on whether its current state is A or B, and the symbol currently being read is 0, 1 or 2. The table entries indicate the symbol to be printed, the direction in which the tape head is to move, and the subsequent state of the machine.

A B
0 P1,R,B P2,L,A
1 P2,L,A P2,R,B
2 P1,L,A P0,R,A

The (2,3) Turing machine:

Minsky (1967) briefly argues that standard (2,2) machines cannot be universal; thus, it might seem that the (2,3) Turing machine would be the smallest possible universal Turing machine (in terms of number of states times number of symbols). However, the results are not directly comparable, because Minsky only considers machines that explicitly halt, which the (2,3) machine does not. More generally, almost all formal definitions of Turing machines differ in details irrelevant to their power, but perhaps relevant to what can be expressed using a given number of states and symbols; there is no single standard formal definition. The (2,3) Turing machine also requires an infinite non-repeating input, again making a direct comparison to earlier small Turing machines problematic.

Therefore, though it may be true that the (2,3) machine is in some sense the "smallest possible universal Turing machine", this has not been strictly proven, and the claim is open to debate.

The state of the head (up or down droplet (A and B respectively)) and the pattern of color (white, yellow and orange (0,1, and 2 respectively)) 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 colors (depending on the initial content of the tape), the machine's output can still be remarkably complex.[3]

Proof of universality

On 24 October 2007, it was announced by Wolfram Research 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.[4][5][6][7][8][9][10][11][12][13][14][15]

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.

Wolfram claims that Smith's proof is another piece of evidence for Wolfram's general Principle of Computational Equivalence (PCE).[16] 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”.[17] 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.[18] 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.

Dispute

The announcement that Alex Smith's proof had won was made without the approval of the judging committee,[19] as noted by Martin Davis, a member of the committee, in a post to the FOM mailing list:

"As far as I know, no member of the committee has passed on the validity of this 40 page proof. The determination that Smith's proof is correct seems to have been made entirely by the Wolfram organization. My understanding is that the I/O involves complex encodings."[20]

Vaughan Pratt subsequently disputed the correctness of this proof in a public list of discussion,[21] noting that similar techniques would allow a linear bounded automaton (or LBA) to be universal, which would contradict a known non-universality result due to Noam Chomsky. Alex Smith joined the mailing list after this message and replied on the following day explaining that a LBA would require to be restarted manually to become universal using the same initial configuration, while his construction restarts the Turing machine automatically with no external intervention.[22] Discussions about the proof continued for some time between Alex Smith, Vaughan Pratt, and others.[23]

See also

References

  1. ↑ Wolfram, Stephen (2002). A New Kind of Science. p. 709. Retrieved 2009-02-10.
  2. ↑ "The Wolfram 2,3 Turing Machine Research Prize". Retrieved 2009-02-10.
  3. ↑ "Student snags maths prize". Natural. 2007. Retrieved 2009-02-10.
  4. ↑ Keim, Brandon (2007-10-24). "College Kid Proves That Wolfram's Turing Machine is the Simplest Universal Computer". Wired. Retrieved 2009-02-10.
  5. ↑ Geoff Brumfiel. "Nature.com". Nature.com. Retrieved 2010-03-09.
  6. ↑ "New Scientist". New Scientist. Retrieved 2010-03-09.
  7. ↑ "Thaindian.com". Thaindian.com. Retrieved 2010-03-09.
  8. ↑ "U of Birmingham". Newscentre.bham.ac.uk. Retrieved 2010-03-09.
  9. ↑ "Math in the news from Math Society". Ams.org. Retrieved 2010-03-09.
  10. ↑ Crighton, Ben (2007-11-26). "Proving Turing's simple computer". BBC News. Retrieved 2010-03-09.
  11. ↑ "Bitwise Mag article". Bitwise Mag article. 2007-10-24. Retrieved 2010-03-09.
  12. ↑ "Mathematical Association of America". Maa.org. Retrieved 2010-03-09.
  13. ↑ Minkel, J. R. (2007-10-25). "A New Kind of Science Author Pays Brainy Undergrad $25,000 for Identifying Simplest Computer". Scientific American. Retrieved 2010-03-09.
  14. ↑ "plus magazine". Plus.maths.org. Retrieved 2010-03-09.
  15. ↑ Stuart, Tom (2007-11-29). "Complex proof of a very simple computer". The Guardian. London. Retrieved 2010-03-09.
  16. ↑ "Stephen Wolfram reply in the FOM list". New York University. October 2007.
  17. ↑ "The Wolfram Prize and Universal Computation: It's Your Problem Now".
  18. ↑ "Simplest 'universal computer' wins student $25,000". New Scientist. 24 October 2007. Retrieved 28 January 2016.
  19. ↑ http://cs.nyu.edu/pipermail/fom/2007-October/012163.html
  20. ↑ http://cs.nyu.edu/pipermail/fom/2007-October/012132.html
  21. ↑ "Vaughan Pratt's message to the FOM list".
  22. ↑ "Alex Smith's first reply to Vaughan Pratt in the FOM list".
  23. ↑ "FOM list archive for November 2007". Cs.nyu.edu. Retrieved 2010-03-09.

Bibliography

Historical reading

External links

This article is issued from Wikipedia - version of the 11/3/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.