View source for Universal Turing machine

{{Short description|Type of Turing machine}}
{{Redirect|Universal machine}}
{{Use dmy dates|date=January 2020}}
{{turing}}
In [[computer science]], a '''universal Turing machine''' ('''UTM''') is a [[Turing machine]] capable of computing any computable sequence,{{sfnp|Turing|1937|p=241}} 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.{{efn|From lecture transcript attributed to [[John von Neumann]], as quoted by Copeland in {{harvp|Copeland|Fan|2023}}. }} He suggested that we may compare a human in the process of computing a real number to a machine which is only capable of a finite number of conditions {{tmath|q_1, q_2, \dots, q_R}}; which will be called "{{mvar|m}}-configurations".{{sfnp|Turing|1937|p=231}} He then described the operation of such machine, as described below, and argued:

{{blockquote|It is my contention that these operations include all those which are used in the computation of a number.{{sfnp|Turing|1937|p=232}} }}

[[Alan Turing|Turing]] introduced the idea of such a machine in 1936–1937.

==Introduction==
{{further|Register machine#Historical development of the register machine model}}
[[Martin Davis (mathematician)|Martin Davis]] makes a persuasive argument that Turing's conception of what is now known as "the stored-program computer", of placing the "action table"—the instructions for the machine—in the same "memory" as the input data, strongly influenced [[John von Neumann]]'s conception of the first American discrete-symbol (as opposed to analog) computer—the [[EDVAC]]. Davis quotes ''Time'' magazine to this effect, that "everyone who taps at a keyboard&nbsp;... is working on an incarnation of a Turing machine", and that "John von Neumann [built] on the work of Alan Turing".{{sfnp|Davis|2000|p=193 quoting ''Time'' magazine of 29 March 1999}}

Davis makes a case that Turing's [[Automatic Computing Engine]] (ACE) computer "anticipated" the notions of microprogramming ([[microcode]]) and [[RISC]] processors.{{sfnp|Davis|2000|p=188}} [[Donald Knuth]] cites Turing's work on the ACE computer as designing "hardware to facilitate subroutine linkage";{{sfnp|Knuth|1973|p=225}} Davis also references this work as Turing's use of a hardware "stack".{{sfnp|Davis|2000|p=237 footnote 18}}

As the Turing machine was encouraging the construction of [[computers]], the UTM was encouraging the development of the fledgling [[computer science]]s. An early, if not the first, assembler was proposed "by a young hot-shot programmer" for the EDVAC.{{sfnp|Davis|2000|p=192}} Von Neumann's "first serious program ... [was] to simply sort data efficiently".{{sfnp|Davis|2000|p=184}} Knuth observes that the subroutine return embedded in the program itself rather than in special registers is attributable to von Neumann and Goldstine.{{efn|In particular: {{harvp|Burks|Goldstine|von Neumann|1971}} [1946].}} Knuth furthermore states that

{{blockquote|The first interpretive routine may be said to be the "Universal Turing Machine" ... Interpretive routines in the conventional sense were mentioned by [[John Mauchly]] in his lectures at the [[Moore School of Electrical Engineering|Moore School]] in 1946 ... Turing took part in this development also; interpretive systems for the Pilot ACE computer were written under his direction.{{sfnp|Knuth|1973|p=226}} }}

Davis briefly mentions operating systems and compilers as outcomes of the notion of program-as-data.{{sfnp|Davis|2000|p=185}}

==Mathematical theory==
With this encoding of action tables as strings, it becomes possible, in principle, for Turing machines to answer questions about the behaviour of other Turing machines. Most of these questions, however, are [[Undecidable problem|undecidable]], meaning that the function in question cannot be calculated mechanically. For instance, the problem of determining whether an arbitrary Turing machine will halt on a particular input, or on all inputs, known as the [[Halting problem]], was shown to be, in general, undecidable in Turing's original paper. [[Rice's theorem]] shows that any non-trivial question about the output of a Turing machine is undecidable.

A universal Turing machine can calculate any [[computable function|recursive function]], decide any [[recursive language]], and accept any [[recursively enumerable language]]. According to the [[Church–Turing thesis]], the problems solvable by a universal Turing machine are exactly those problems solvable by an ''[[algorithm]]'' or an ''effective method of computation'', for any reasonable definition of those terms.  For these reasons, a universal Turing machine serves as a standard against which to compare computational systems, and a system that can simulate a universal Turing machine is called [[Turing complete]].

An abstract version of the universal Turing machine is the [[Utm theorem|universal function]], a computable function which can be used to calculate any other computable function. The [[UTM theorem]] proves the existence of such a function.

==Efficiency==
Without loss of generality, the input of Turing machine can be assumed to be in the alphabet {0, 1}; any other finite alphabet can be encoded over {0, 1}. The behavior of a Turing machine ''M'' is determined by its transition function. This function can be easily encoded as a string over the alphabet {0, 1} as well. The size of the alphabet of ''M'', the number of tapes it has, and the size of the state space can be deduced from the transition function's table. The distinguished states and symbols can be identified by their position, e.g. the first two states can by convention be the start and stop states. Consequently, every Turing machine can be encoded as a string over the alphabet {0, 1}. Additionally, we convene that every invalid encoding maps to a trivial Turing machine that immediately halts, and that every Turing machine can have an infinite number of encodings by padding the encoding with an arbitrary number of (say) 1's at the end, just like comments work in a programming language. It should be no surprise that we can achieve this encoding given the existence of a [[Gödel number]] and computational equivalence between Turing machines and [[μ-recursive function]]s. Similarly, our construction associates to every binary string ''α'', a Turing machine ''M<sub>α</sub>''.

Starting from the above encoding, in 1966 F. C. Hennie and [[Richard E. Stearns|R. E. Stearns]] showed that given a Turing machine ''M<sub>α</sub>'' that halts on input ''x'' within ''N'' steps, then there exists a multi-tape universal Turing machine that halts on inputs ''α'', ''x'' (given on different tapes) in ''CN'' log ''N'', where ''C'' is a machine-specific constant that does not depend on the length of the input ''x'', but does depend on ''M'''s alphabet size, number of tapes, and number of states. Effectively this is an <math>\mathcal{O}\left ( N \log {N}\right )</math> simulation, using [[Donald Knuth]]'s [[Big O notation]].{{sfnp|Arora|Barak|2009|loc=Theorem 1.9}} The corresponding result for space-complexity rather than time-complexity is that we can simulate in a way that uses at most ''CN'' cells at any stage of the computation, an <math>\mathcal{O}(N)</math> simulation.{{sfnp|Arora|Barak|2009|loc=Exercises 4.1}}

==Smallest machines==
When Alan Turing came up with the idea of a universal machine he had in mind the simplest computing model powerful enough to calculate all possible functions that can be calculated. [[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. He also showed that no universal Turing machine of one state could exist.

[[Marvin Minsky]] discovered a 7-state 4-symbol universal Turing machine in 1962 using [[tag system|2-tag systems]]. Other small universal Turing machines have since been found by Yurii Rogozhin and others by extending this approach of tag system simulation. If we denote by (''m'', ''n'') the class of UTMs with ''m'' states and ''n'' symbols the following tuples have been found: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), and (2, 18).{{sfnp|Rogozhin|1996}}{{sfnp|Kudlek|Rogozhin|2002}}{{sfnp|Neary|Woods|2009}} Rogozhin's (4, 6) machine uses only 22 instructions, and no standard UTM of lesser descriptional complexity is known.

However, generalizing the standard Turing machine model admits even smaller UTMs. One such generalization is to allow an infinitely repeated word on one or both sides of the Turing machine input, thus extending the definition of universality and known as "semi-weak" or "weak" universality, respectively. Small weakly universal Turing machines that simulate the [[Rule 110]] cellular automaton have been given for the (6, 2), (3, 3), and (2, 4) state-symbol pairs.{{sfnp|Neary|Woods|2009b}} The proof of universality for [[Wolfram's 2-state 3-symbol Turing machine]] further extends the notion of weak universality by allowing certain non-periodic initial configurations. Other variants on the standard Turing machine model that yield small UTMs include machines with multiple tapes or tapes of multiple dimension, and machines coupled with a [[finite automaton]].

==Machines with no internal states==
If multiple heads are allowed on a Turing machine then no internal states are required; as "states" can be encoded in the tape. For example, consider a tape with 6 colours: 0, 1, 2, 0A, 1A, 2A. Consider a tape such as 0,0,1,2,2A,0,2,1 where a 3-headed Turing machine is situated over the triple (2,2A,0). The rules then convert any triple to another triple and move the 3-heads left or right. For example, the rules might convert (2,2A,0) to (2,1,0) and move the head left. Thus in this example, the machine acts like a 3-colour Turing machine with internal states A and B (represented by no letter). The case for a 2-headed Turing machine is very similar. Thus a 2-headed Turing machine can be Universal with 6 colours. It is not known what the smallest number of colours needed for a multi-headed Turing machine is or if a 2-colour Universal Turing machine is possible with multiple heads. It also means that [[Rewriting|rewrite rules]] are Turing complete since the triple rules are equivalent to rewrite rules. Extending the tape to two dimensions with a head sampling a letter and its 8 neighbours, only 2 colours are needed, as for example, a colour can be encoded in a vertical triple pattern such as 110.

Also, if the distance between the two heads is variable (the tape has "slack" between the heads), then it can simulate any [[Tag system|Post tag system]], some of which are universal.{{sfnp|Minsky|1967|p=269}}

==Example of coding==
For those who would undertake the challenge of designing a UTM exactly as Turing specified see the article by Davies in {{harvp|Copeland|2004}}. Davies corrects the errors in the original and shows what a sample run would look like. He successfully ran a (somewhat simplified) simulation.

The following example is taken from {{harvp|Turing|1937}}. For more about this example, see [[Turing machine examples]].

Turing used seven symbols { A, C, D, R, L, N, ; } to encode each 5-tuple; as described in the article [[Turing machine]], his 5-tuples are only of types N1, N2, and N3. The number of each "{{mvar|m}}{{nbh}}configuration" (instruction, state) is represented by "D" followed by a unary string of A's, e.g. "q3" = DAAA. In a similar manner, he encodes the symbols blank as "D", the symbol "0" as "DC", the symbol "1" as DCC, etc. The symbols "R", "L", and "N" remain as is.

After encoding each 5-tuple is then "assembled" into a string in order as shown in the following table:

{|class="wikitable"
|-
! Current m{{nbh}}configuration
! Tape symbol
! Print-operation
! Tape-motion
! Final m{{nbh}}configuration
! Current m{{nbh}}configuration code
! Tape symbol code
! Print-operation code
! Tape-motion code
! Final m{{nbh}}configuration code
! 5-tuple assembled code
|-
| q1
 | {{CNone|blank}}
 | P0
 | R
 | q2
 | DA
 | D
 | DC
 | R
 | DAA
 | DADDCRDAA
|-
| q2
 | {{CNone|blank}}
 | E
 | R
 | q3
 | DAA
 | D
 | D
 | R
 | DAAA
 | DAADDRDAAA
|-
| q3
 | {{CNone|blank}}
 | P1
 | R
 | q4
 | DAAA
 | D
 | DCC
 | R
 | DAAAA
 | DAAADDCCRDAAAA
|-
| q4
 | {{CNone|blank}}
 | E
 | R
 | q1
 | DAAAA
 | D
 | D
 | R
 | DA
 | DAAAADDRDA
|}

Finally, the codes for all four 5-tuples are strung together into a code started by ";" and separated by ";" i.e.:

{{block indent| ''';'''DADDCRDAA''';'''DAADDRDAAA''';'''DAAADDCCRDAAAA''';'''DAAAADDRDA}}

This code he placed on alternate squares—the "F-squares" – leaving the "E-squares" (those liable to erasure) empty. The final assembly of the code on the tape for the U-machine consists of placing two special symbols ("e") one after the other, then the code separated out on alternate squares, and lastly the double-colon symbol "'''::'''" (blanks shown here with "." for clarity):

{{block indent|ee.''';'''.D.A.D.D.C.R.D.A.A.''';'''.D.A.A.D.D.R.D.A.A.A.''';'''.D.A.A.A.D.D.C.C.R.D.A.A.A.A.''';'''.D.A.A.A.A.D.D.R.D.A.'''::'''......}}

The U-machine's action-table (state-transition table) is responsible for decoding the symbols. Turing's action table keeps track of its place with markers "u", "v", "x", "y", "z" by placing them in "E-squares" to the right of "the marked symbol" – for example, to mark the current instruction '''z''' is placed to the right of ";"  '''x''' is keeping the place with respect to the current "m{{nbh}}configuration" DAA. The U-machine's action table will shuttle these symbols around (erasing them and placing them in different locations) as the computation progresses:

{{block indent|ee.''';''' .D.A.D.D.C.R.D.A.A. ''';''' '''z'''D.A.A'''x'''D.D.R.D.A.A.A.''';'''.D.A.A.A.D.D.C.C.R.D.A.A.A.A.''';'''.D.A.A.A.A.D.D.R.D.A.'''::'''......}}

Turing's action-table for his U-machine is very involved.

[[Roger Penrose]] provides examples of ways to encode instructions for the Universal machine using only binary symbols { 0, 1 }, or { blank, mark | }. Penrose goes further and writes out his entire U-machine code. He asserts that it truly is a U-machine code, an enormous number that spans almost 2 full pages of 1's and 0's.{{sfnp|Penrose|1989|pp=71–73}}

Asperti and Ricciotti described a multi-tape UTM defined by composing elementary machines with very simple semantics, rather than explicitly giving its full action table. This approach was sufficiently modular to allow them to formally prove the correctness of the machine in the [[Matita]] proof assistant.{{sfnp|Asperti|Ricciotti|2015}}

==See also==
* {{anli|Alternating Turing machine}}
* {{anli|Counter machine}}
* {{anli|Kleene's T predicate}}
* {{anli|Mark and space}}
* {{anli|Turing machine equivalents}}
* {{anli|Von Neumann universal constructor}}

==Notes==
{{notelist}}

==References==
===Footnotes===
{{Reflist|15em}}
===Original paper and correction===
* {{cite journal |url=http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf |title=On Computable Numbers, with an Application to the Entscheidungsproblem |date=1937 |journal=Proceedings of the London Mathematical Society |series=2 |volume=42 |issue=1 |last= Turing |first=A. M. |author-link=Alan Turing |pages=230–265 |doi=10.1112/plms/s2-42.1.230}}
* {{Cite journal |last=Turing |first=A. M. |date=1938 |title=On Computable Numbers, with an Application to the Entscheidungsproblem: A correction |periodical=Proceedings of the London Mathematical Society |series=2 |volume=43 |issue=6 |pages=544–6 |doi=10.1112/plms/s2-43.6.544}}

===Other works cited===
{{refbegin|indent=yes}}
* {{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |quote= section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9" }}
* {{cite journal
 | last1 = Asperti | first1 = Andrea
 | last2 = Ricciotti | first2 = Wilmer
 | doi = 10.1016/j.tcs.2015.07.013
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 3406235
 | pages = 23–42
 | title = A formalization of multi-tape Turing machines
 | volume = 603
 | year = 2015| hdl = 11585/536349
 | hdl-access = free
 }}
* {{Cite book |last1=Burks |first1=Arthur W. |last2=Goldstine |first2=Herman H. |last3=von Neumann |first3=John |chapter=Planning and Coding of the Problems for an Electronic Computing Instrument |orig-year=1946 |pages=92–119 |editor-last1=Bell |editor-first1=C. Gordon |editor-last2=Newell |editor-first2=Allen |date=1971 |title=Computer Structures: Readings and Examples |publisher=McGraw-Hill Book Company |location=New York |isbn=0-07-004357-4 |chapter-url-access=registration |chapter-url=https://archive.org/details/computerstructur00bell/page/92}}
* {{Cite book |editor-last=Copeland |editor-first=Jack |editor-link=Jack Copeland  |title=The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma |year=2004 |place = Oxford UK |publisher=Oxford University Press |isbn=0-19-825079-7}}
* {{Cite journal |last1=Copeland |first1=B. J. |last2=Fan |first2=Z. |title=Turing and Von Neumann: From Logic to the Computer |journal=Philosophies |year=2023 |volume=8 |number=22 |page=22 |doi=10.3390/philosophies8020022|doi-access=free }}
* {{Cite book |first=Martin |last=Davis |author-link=Martin Davis (mathematician) |contribution=What is Computation? |editor-first=Lynn Arthur |editor-last=Steen |editor-link=Lynn Steen |title=Mathematics Today: Twelve Informal Essays |year =1980 |place=New York |publisher=Vintage Books (Random House) |isbn=978-0-394-74503-9 |url-access=registration |url=https://archive.org/details/mathematicstoday00stee}}
* {{Cite book |first=Martin |last=Davis  |title=Engines of Logic: Mathematicians and the origin of the Computer |edition=1st |year=2000 |place=New York |publisher=W. W. Norton & Company |isbn=0-393-32229-7}}
* {{Cite journal | last1 = Hennie | first1 = F. C. | last2 = Stearns | first2 = R. E. | doi = 10.1145/321356.321362 | title = Two-Tape Simulation of Multitape Turing Machines | journal = Journal of the ACM | volume = 13 | issue = 4 | pages = 533 | year = 1966 | s2cid = 2347143 }}
* {{Cite book |last=Knuth |first=Donald E. |author-link=Donald Knuth |title=The Art of Computer Programming |edition=second |volume=1: Fundamental Algorithms |publisher=Addison-Wesley Publishing Company |date=1973}} 
* {{Cite conference |first1=Manfred |last1=Kudlek |first2=Yurii |last2=Rogozhin |contribution=A universal Turing machine with 3 states and 9 symbols |title=Developments in Language Theory: 5th International Conference, DLT 2001 Wien, Austria, July 16–21, 2001, Revised Papers |editor1-first=Werner |editor1-last=Kuich |editor2-first=Grzegorz |editor2-last=Rozenberg |editor3-first=Arto |editor3-last=Salomaa |volume=2295 |publisher=Springer |year=2002 |pages=311–318 |doi=10.1007/3-540-46011-x_27 |series=Lecture Notes in Computer Science |isbn=978-3-540-43453-5}}
* {{Cite book |last=Minsky |first=Marvin Lee |title=Computation: Finite and Infinite Machines |year=1967 |publisher=Prentice Hall |isbn=978-0-13-165563-8}}
* {{Cite journal |first1=Turlough |last1=Neary |first2=Damien |last2=Woods |title=Four Small Universal Turing Machines |journal=Fundamenta Informaticae |volume=91 |issue=1 |year=2009 |pages=123–144 |doi=10.3233/FI-2009-0036 |url=http://mural.maynoothuniversity.ie/12416/1/Woods_FourSmall_2009.pdf}}
* {{Cite book |first1=Turlough |last1=Neary |first2=Damien |last2=Woods |contribution=Small Weakly Universal Turing Machines |title=17th International Symposium on Fundamentals of Computation Theory |title-link=International Symposium on Fundamentals of Computation Theory |pages=262–273 |publisher=Springer |series=Lecture Notes in Computer Science |volume= 5699 |year=2009b}}
* {{Cite book |first=Roger |last=Penrose |author-link=Roger Penrose |title=The Emperor's New Mind |year=1989 |place=Oxford UK |publisher=Oxford University Press | isbn=0-19-851973-7 |title-link=The Emperor's New Mind}}
* {{Cite journal |first=Yurii |last=Rogozhin |title=Small Universal Turing Machines |journal=Theoretical Computer Science |year=1996 |volume=168 |pages=215–240 |issue=2 |doi=10.1016/S0304-3975(96)00077-1 |doi-access=free}}
{{refend}}

==Further reading==
{{refbegin|indent=yes}}
*{{Cite book |first=M. A. |last=Arbib |year=1988 |chapter=From universal Turing machines to self-reproduction |editor-last=Herken |editor-first=R. |title=A half-century survey on The Universal Turing Machine |publisher=Oxford University Press |pages=177–189 |isbn=978-0-19-853741-0 |ref=none}}
*{{Cite book |editor-first=Martin |editor-last=Davis |date=1965 |title=The Undecidable |publisher=Raven Press |location=Hewlett, New York |url=https://archive.org/details/undecidablebasic0000davi |url-access=registration |ref=none}}
* {{Cite book |last=Davis |first=Martin|year=2018 |title=The Universal Computer: The Road from Leibniz to Turing |publisher=Taylor & Francis Group |isbn=978-1138413931}}
*{{Cite book | first = Rolf | last = Herken | title = The Universal Turing Machine: A Half-Century Survey | year =1995 | publisher = Springer Verlag | isbn = 3-211-82637-8 |ref=none}}
*{{Cite book | first = Marvin | last = Minsky | title = Recursive Function Theory | chapter = Size and structure of universal Turing machines using tag systems | series = Proceedings of Symposia in Pure Mathematics | author-link = Marvin Minsky | year = 1962 | pages = 229–238 | place = Providence RI | publisher = American Mathematical Society | volume = 5 | doi = 10.1090/pspum/005/0142452 | doi-access = free | isbn = 978-0-8218-1405-5 |ref=none}}
*{{Cite book | first = Claude | last = Shannon | author-link = Claude Shannon | title = Automata Studies | contribution = A Universal Turing Machine with Two Internal States | year = 1956 | pages = 157–165 | publisher = Princeton University Press | place = Princeton, NJ |ref=none}}
{{refend}}

==External links==
*{{cite web |url=http://alvyray.com/CreativeCommons/BizCardUniversalTuringMachine_v2.3.pdf |title=A Business Card Universal Turing Machine |last=Smith |first=Alvy Ray|access-date=2 January 2020}}
{{Authority control}}

{{DEFAULTSORT:Universal Turing Machine}}
[[Category:Turing machine]]