TOPICS
Search

Universal Turing Machine


UniversalTuringMachine7-4Rules

A Turing machine which, by appropriate programming using a finite length of input tape, can act as any Turing machine whatsoever. In his seminal paper, Turing himself gave the first construction for a universal Turing machine (Turing 1937, 1938). Shannon (1956) showed that two colors were sufficient, so long as enough states were used. Minsky (1962) discovered a 7-state 4-color universal Turing machine, illustrated above (Wolfram 2002, p. 706). Note that the 20th rule specifies that the Turing machine should halt, as indicated by leaving the head stationary and not changing its state. Upon conversion to a 2-color machine, Minsky's universal Turing machine requires 43 states.

Comparatively little more was published about small universal Turing machines until Rogozhin (1996) found examples with the numbers (m,n) of states m and colors n given by (24, 2), (10, 3), (7, 4), (5, 5), (4, 6), (3, 10), and (2, 18) (Wolfram 2002, p. 1119).

UniversalTuringMachine2-5Rules

A 2-state 5-color universal Turing machine, illustrated above, was discovered by Wolfram (2002, p. 707). This example has the smallest product mn=10 of any other known universal Turing machine. However, there very likely exist examples that are smaller still.

UniversalTuringMachine2-4Rules
UniversalTuringMachine2-3Rules

Four 2-state 4-color and 14 essentially equivalent 2-state 3-color machines identified by Wolfram (2002, pp. 708-709) are likely universal, although this appears difficult to prove. On May 14, 2007, Wolfram Research and Stephen Wolfram announced a $25,000 cash prize for a proof that this Turing machine is in fact universal. On Oct. 24, 2007, Alex Smith claimed the prize with a successful proof (Smith 2020).


See also

Chaitin's Constant, Halting Problem, Turing Machine, Universal Cellular Automaton, Universality

Explore with Wolfram|Alpha

References

Minsky, M. L. "Some Universal Elements for Finite Automata." Automata Studies. Princeton, NJ: Princeton University Press, pp. 117-128, 1956.Minsky, M. L. "Size and Structure of Universal Turing Machines Using Tag Systems." Proc. Sympos. Pure Math. 5, 229-238, 1962.Ord, T. "Hypercomputation: Computing More Than the Turing Machine." 25 Sep 2002. http://arxiv.org/abs/math.LO/0209332.Penrose, R. The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics. Oxford: Oxford University Press, pp. 51-57, 1989.Rogozhin, Yu. V. "Seven Universal Turing Machines." Mat. Issled., No. 69, 76-90, 1982.Rogozhin, Yu. V. "A Universal Turing Machine with 10 States and 3 Symbols." Izv. Akad. Nauk Respub. Moldova Mat., No. 4, 80-82 and 95, 1992.Rogozhin, Yu. "Small Universal Turing Machines." Theoret. Comput. Sci. 168, 215-240, 1996.Shannon, C. E. "A Universal Turing Machine with Two Internal States." Automata Studies. Princeton, NJ: Princeton University Press, pp. 157-165, 1956.Smith, A. "Universality of Wolfram's 2, 3 Turing Machine." Complex Systems 29, 1-44, 2020. Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 42, 230-265, 1937. Reprinted in The Undecidable (Ed. M. David). Hewlett, NY: Raven Press, 1965.Turing, A. M. "Correction to: On Computable Numbers, with an Application to the Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 43, 544-546, 1938.Wolfram Research and Wolfram, S. "The Wolfram 2,3 Turing Machine Research Prize." http://www.wolframscience.com/prizes/tm23/.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 706-711 and 1119, 2002.

Referenced on Wolfram|Alpha

Universal Turing Machine

Cite this as:

Weisstein, Eric W. "Universal Turing Machine." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UniversalTuringMachine.html

Subject classifications