Wolfram's 2-state 3-symbol Turing machine

Last updated

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]

Contents

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

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.

AB
0P1,R,BP2,L,A
1P2,L,AP2,R,B
2P1,L,AP0,R,A

The (2,3) Turing machine:

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

2-state 3-symbol Turing Machine.png

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

Related Research Articles

<span class="mw-page-title-main">Algorithm</span> Sequence of operations for a task

In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes and deduce valid inferences, achieving automation eventually. Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus".

A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computations are mathematical equations and computer algorithms.

In computability theory, the Church–Turing thesis is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods. In the 1930s, several independent attempts were made to formalize the notion of computability:

<span class="mw-page-title-main">Turing machine</span> Computation model defining an abstract machine

A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm.

In computability theory, a system of data-manipulation rules is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine. This means that this system is able to recognize or decide other data-manipulation rule sets. Turing completeness is used as a way to express the power of such a data-manipulation rule set. Virtually all programming languages today are Turing-complete.

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

<span class="mw-page-title-main">Wolfram Mathematica</span> Computational software program

Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimization, plotting functions and various types of data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other programming languages. It was conceived by Stephen Wolfram, and is developed by Wolfram Research of Champaign, Illinois. The Wolfram Language is the programming language used in Mathematica. Mathematica 1.0 was released on June 23, 1988 in Champaign, Illinois and Santa Clara, California.

<span class="mw-page-title-main">Cellular automaton</span> Discrete model studied in computer science

A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.

In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game. This is sometimes also formulated as finding the machine that runs for the longest time, but both games are similarly difficult.

In computer science, a universal Turing machine (UTM) is a Turing machine capable of computing any computable sequence, as described by Alan Turing in his seminal paper "On Computable Numbers, with an Application to the Entscheidungsproblem". Common sense might say that a universal machine is impossible, but Turing proves that it is possible. He suggested that we may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q 1: q 2. .... qI; which will be called "m-configurations". He then described the operation of such machine, as described below, and argued:

It is my contention that these operations include all those which are used in the computation of a number.

<i>A New Kind of Science</i> Book by Stephen Wolfram

A New Kind of Science is a book by Stephen Wolfram, published by his company Wolfram Research under the imprint Wolfram Media in 2002. It contains an empirical and systematic study of computational systems such as cellular automata. Wolfram calls these systems simple programs and argues that the scientific philosophy and methods appropriate for the study of simple programs are relevant to other fields of science.

<span class="mw-page-title-main">Langton's ant</span> Two-dimensional Turing machine with emergent behavior

Langton's ant is a two-dimensional universal Turing machine with a very simple set of rules but complex emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000. The idea has been generalized in several different ways, such as turmites which add more colors and more states.

Matthew Cook is a mathematician and computer scientist who is best known for having proved Stephen Wolfram's conjecture that the Rule 110 cellular automaton is Turing-complete.

In the theory of computation, a tag system is a deterministic model of computation published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine —briefly, a finite-state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition.

Solomonoff's theory of inductive inference is a mathematical theory of induction introduced by Ray Solomonoff, based on probability theory and theoretical computer science. In essence, Solomonoff's induction derives the posterior probability of any computable theory, given a sequence of observed data. This posterior probability is derived from Bayes' rule and some universal prior, that is, a prior that assigns a positive probability to any computable theory.

<span class="mw-page-title-main">Rule 110</span> Elementary cellular automaton

The Rule 110 cellular automaton is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 with a particular repeating background pattern is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.

<span class="mw-page-title-main">Shafi Goldwasser</span> Israeli American computer scientist

Shafrira Goldwasser is an Israeli-American computer scientist and winner of the Turing Award in 2012. She is the RSA Professor of Electrical Engineering and Computer Science at Massachusetts Institute of Technology; a professor of mathematical sciences at the Weizmann Institute of Science, Israel; the director of the Simons Institute for the Theory of Computing at the University of California, Berkeley; and co-founder and chief scientist of Duality Technologies.

<span class="mw-page-title-main">History of computer science</span> Aspect of history

The history of computer science began long before the modern discipline of computer science, usually appearing in forms like mathematics or physics. Developments in previous centuries alluded to the discipline that we now know as computer science. This progression, from mechanical inventions and mathematical theories towards modern computer concepts and machines, led to the development of a major academic field, massive technological advancement across the Western world, and the basis of a massive worldwide trade and culture.

In computability theory, super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. The term was introduced by Mark Burgin, whose book "Super-recursive algorithms" develops their theory and presents several mathematical models. Turing machines and other mathematical models of conventional algorithms allow researchers to find properties of recursive algorithms and their computations. In a similar way, mathematical models of super-recursive algorithms, such as inductive Turing machines, allow researchers to find properties of super-recursive algorithms and their computations.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs.

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. 30 October 2007. Retrieved 18 August 2022.
  21. ↑ "[FOM] Smallest universal machine". Cs.nyu.edu. 26 October 2007. Retrieved 18 August 2022.
  22. ↑ "Vaughan Pratt's message to the FOM list". 29 October 2007.
  23. ↑ "Alex Smith's first reply to Vaughan Pratt in the FOM list". 30 October 2007.
  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. S2CID   17142621.

Bibliography

Historical reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.