fbpx
Wikipedia

Wolfram's 2-state 3-symbol Turing machine

January 07, 2023

In his book A New Kind of Science, Stephen Wolfram described a universal 2-state 5-symbol 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. Since the proof applies to a non-standard Turing machine model which allows infinite, non-periodic initial configurations, it is categorized by some as "weak-universal".[3]

Background

See also: Universal_Turing_machine § Smallest_machines

Claude Shannon first explicitly posed the question of finding the smallest possible universal Turing machine in 1956. He showed that two symbols were sufficient so long as enough states were used (or vice versa), and that it was always possible to exchange states for symbols.

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:

  • Has no halt state;
  • Is trivially related to 23 other machines by interchange of states, symbols and directions.

Minsky (1967) briefly argued that standard (2,2) machines cannot be universal and M. Margenstern (2010) provided a mathematical proof[4] based on a result by L. Pavlotskaya in 1973 (not published but mentioned in Margenstern article); 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 universal 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 in the classical sense, and the claim is open to debate when taking into consideration traditional definitions of universality and whether the relaxing of the Turing machine properties used for the proof can be allowed in general and may even suggest novel ways to define computational universality more independent of arbitrary choices (such as having a halting configuration or requiring a blank tape).

 

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 arbitrarily complex.[5]

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.[6][7][8][9][10][11][12][13][14][15][16]

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).[17] 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".[18] 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.[19] 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,[20] 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."[21]

Vaughan Pratt subsequently disputed the correctness of this proof in a post to the mailing list,[22] 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.[23] Discussions about the proof continued for some time between Alex Smith, Vaughan Pratt, and others.[24]

Publication

Smith's proof was finally published in Wolfram's journal Complex Systems in 2020.[25]

See also

References

  1. ^ Wolfram, Stephen (2002). A New Kind of Science. p. 709. Retrieved 10 February 2009.
  2. ^ "The Wolfram 2,3 Turing Machine Research Prize". Retrieved 10 February 2009.
  3. ^ Goodman-Strauss, Chaim, Can't decide? Undecide!, CiteSeerX 10.1.1.164.306, retrieved 4 February 2022
  4. ^ "Turing Machines with Two Letters and Two States". Complex Systems. 2010. Retrieved 25 October 2017.
  5. ^ Brumfiel, Geoff (2007). "Student snags maths prize". Nature. doi:10.1038/news.2007.190. Retrieved 10 February 2009.
  6. ^ Keim, Brandon (24 October 2007). "College Kid Proves That Wolfram's Turing Machine is the Simplest Universal Computer". Wired. Retrieved 10 February 2009.
  7. ^ Geoff Brumfiel (24 October 2007). "Nature.com". Nature. Nature.com. doi:10.1038/news.2007.190. Retrieved 9 March 2010.
  8. ^ "New Scientist". New Scientist. Retrieved 9 March 2010.
  9. ^ "U of Birmingham". Newscentre.bham.ac.uk. Retrieved 9 March 2010.
  10. ^ "Math in the news from Math Society". Ams.org. Retrieved 9 March 2010.
  11. ^ Crighton, Ben (26 November 2007). "Proving Turing's simple computer". BBC News. Retrieved 9 March 2010.
  12. ^ "Bitwise Mag article". Bitwise Mag article. 24 October 2007. Retrieved 9 March 2010.
  13. ^ "Mathematical Association of America". Maa.org. Retrieved 9 March 2010.
  14. ^ Minkel, J. R. (25 October 2007). "A New Kind of Science Author Pays Brainy Undergrad $25,000 for Identifying Simplest Computer". Scientific American. Retrieved 9 March 2010.
  15. ^ "plus magazine". Plus.maths.org. 8 November 2007. Retrieved 9 March 2010.
  16. ^ Stuart, Tom (29 November 2007). "Complex proof of a very simple computer". The Guardian. London. Retrieved 9 March 2010.
  17. ^ "Stephen Wolfram reply in the FOM list". New York University. October 2007.
  18. ^ "The Wolfram Prize and Universal Computation: It's Your Problem Now".
  19. ^ "Simplest 'universal computer' wins student $25,000". New Scientist. 24 October 2007. Retrieved 28 January 2016.
  20. ^ "[FOM] Smallest universal machine". Cs.nyu.edu. Retrieved 18 August 2022.
  21. ^ "[FOM] Smallest universal machine". Cs.nyu.edu. Retrieved 18 August 2022.
  22. ^ "Vaughan Pratt's message to the FOM list".
  23. ^ "Alex Smith's first reply to Vaughan Pratt in the FOM list".
  24. ^ "FOM list archive for November 2007". Cs.nyu.edu. Retrieved 9 March 2010.
  25. ^ Smith, Alex (2020). "Universality of Wolfram's 2, 3 Turing Machine". Complex Systems. 29 (1): 1–44. doi:10.25088/ComplexSystems.29.1.1.

Bibliography

  • Wolfram, S (2002) A New Kind of Science. Wolfram Media.
  • Wolfram Research, Inc., "Prize Announced for Determining the Boundaries of Turing Machine Computation". Formal announcement that Alex Smith has won the prize.
  • —, 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) "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

  • "Student snags maths prize" Nature. Published online 24 October 2007.
  • "College Kid Proves That Wolfram's Turing Machine is the Simplest Universal Computer," Wired Science. Published online 24 October 2007.
  • "Simplest 'universal computer' wins student $25,000," New Scientist. Published online 24 October 2007.
  • "The Wolfram Prize and Universal Computation: It's Your Problem Now," Dr. Dobb's Journal. Published online 22 October 2007.
  • Minkel, J.R., "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:
    • Simple Turing machines, Universality, Encodings, etc.
    • Simplest universal Turing Machine
    • Smallest universal machine
    • Vaughan Pratt's claim that Smith's proof is invalid
    • Wolfram's reply to Pratt in the same forum
    • Reply to Pratt by Todd Rowland, one of the judges for the prize

January 07, 2023
wolfram, state, symbol, turing, machine, book, kind, science, stephen, wolfram, described, universal, state, symbol, turing, machine, conjectured, that, particular, state, symbol, turing, machine, hereinafter, turing, machine, might, universal, well, 2007, wol. In his book A New Kind of Science Stephen Wolfram described a universal 2 state 5 symbol 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 Since the proof applies to a non standard Turing machine model which allows infinite non periodic initial configurations it is categorized by some as weak universal 3 Contents 1 Background 2 Proof of universality 2 1 Dispute 2 2 Publication 3 See also 4 References 5 Bibliography 6 Historical reading 7 External linksBackground EditSee also Universal Turing machine Smallest machines Claude Shannon first explicitly posed the question of finding the smallest possible universal Turing machine in 1956 He showed that two symbols were sufficient so long as enough states were used or vice versa and that it was always possible to exchange states for symbols 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 B0 P1 R B P2 L A1 P2 L A P2 R B2 P1 L A P0 R AThe 2 3 Turing machine Has no halt state Is trivially related to 23 other machines by interchange of states symbols and directions Minsky 1967 briefly argued that standard 2 2 machines cannot be universal and M Margenstern 2010 provided a mathematical proof 4 based on a result by L Pavlotskaya in 1973 not published but mentioned in Margenstern article 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 universal 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 in the classical sense and the claim is open to debate when taking into consideration traditional definitions of universality and whether the relaxing of the Turing machine properties used for the proof can be allowed in general and may even suggest novel ways to define computational universality more independent of arbitrary choices such as having a halting configuration or requiring a blank tape 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 arbitrarily complex 5 Proof of universality EditOn 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 6 7 8 9 10 11 12 13 14 15 16 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 17 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 18 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 19 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 Edit The announcement that Alex Smith s proof had won was made without the approval of the judging committee 20 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 21 Vaughan Pratt subsequently disputed the correctness of this proof in a post to the mailing list 22 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 23 Discussions about the proof continued for some time between Alex Smith Vaughan Pratt and others 24 Publication Edit Smith s proof was finally published in Wolfram s journal Complex Systems in 2020 25 See also EditTuring completeness the ability of simulating any Turing machine Rule 110 a Turing complete elementary cellular automatonReferences Edit Wolfram Stephen 2002 A New Kind of Science p 709 Retrieved 10 February 2009 The Wolfram 2 3 Turing Machine Research Prize Retrieved 10 February 2009 Goodman Strauss Chaim Can t decide Undecide CiteSeerX 10 1 1 164 306 retrieved 4 February 2022 Turing Machines with Two Letters and Two States Complex Systems 2010 Retrieved 25 October 2017 Brumfiel Geoff 2007 Student snags maths prize Nature doi 10 1038 news 2007 190 Retrieved 10 February 2009 Keim Brandon 24 October 2007 College Kid Proves That Wolfram s Turing Machine is the Simplest Universal Computer Wired Retrieved 10 February 2009 Geoff Brumfiel 24 October 2007 Nature com Nature Nature com doi 10 1038 news 2007 190 Retrieved 9 March 2010 New Scientist New Scientist Retrieved 9 March 2010 U of Birmingham Newscentre bham ac uk Retrieved 9 March 2010 Math in the news from Math Society Ams org Retrieved 9 March 2010 Crighton Ben 26 November 2007 Proving Turing s simple computer BBC News Retrieved 9 March 2010 Bitwise Mag article Bitwise Mag article 24 October 2007 Retrieved 9 March 2010 Mathematical Association of America Maa org Retrieved 9 March 2010 Minkel J R 25 October 2007 A New Kind of Science Author Pays Brainy Undergrad 25 000 for Identifying Simplest Computer Scientific American Retrieved 9 March 2010 plus magazine Plus maths org 8 November 2007 Retrieved 9 March 2010 Stuart Tom 29 November 2007 Complex proof of a very simple computer The Guardian London Retrieved 9 March 2010 Stephen Wolfram reply in the FOM list New York University October 2007 The Wolfram Prize and Universal Computation It s Your Problem Now Simplest universal computer wins student 25 000 New Scientist 24 October 2007 Retrieved 28 January 2016 FOM Smallest universal machine Cs nyu edu Retrieved 18 August 2022 FOM Smallest universal machine Cs nyu edu Retrieved 18 August 2022 Vaughan Pratt s message to the FOM list Alex Smith s first reply to Vaughan Pratt in the FOM list FOM list archive for November 2007 Cs nyu edu Retrieved 9 March 2010 Smith Alex 2020 Universality of Wolfram s 2 3 Turing Machine Complex Systems 29 1 1 44 doi 10 25088 ComplexSystems 29 1 1 Bibliography EditWolfram S 2002 A New Kind of Science Wolfram Media Wolfram Research Inc Prize Announced for Determining the Boundaries of Turing Machine Computation Formal announcement that Alex Smith has won the prize Wolfram 2 3 Turing Machine Research Prize Invitation to contestants Historical reading EditMarvin Minsky 1967 Computation Finite and Infinite Machines Prentice Hall Turing A 1937 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 Edit Student snags maths prize Nature Published online 24 October 2007 College Kid Proves That Wolfram s Turing Machine is the Simplest Universal Computer Wired Science Published online 24 October 2007 Simplest universal computer wins student 25 000 New Scientist Published online 24 October 2007 The Wolfram Prize and Universal Computation It s Your Problem Now Dr Dobb s Journal Published online 22 October 2007 Minkel J R 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 Simple Turing machines Universality Encodings etc Simplest universal Turing Machine Smallest universal machine Vaughan Pratt s claim that Smith s proof is invalid Wolfram s reply to Pratt in the same forum Reply to Pratt by Todd Rowland one of the judges for the prize Retrieved from https en wikipedia org w index php title Wolfram 27s 2 state 3 symbol Turing machine amp oldid 1105116695, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.