- Universal Turing machine
:"This article is a supplement to the article

Turing machine ."Alan Turing 's "universal computing machine" (alternately "universal machine", "machine U", "U") is the name given by him (1936-1937) to his model of an all-purpose "a-machine" (computing machine) that could "run" any arbitrary (but well-formed) sequence of instructions called "quintuples". This model is considered by some (e.g., Davis (2000)) to be the origin of the "stored program computer" -- used byJohn von Neumann (1946) for his "Electronic Computing Instrument" that now bears von Neumann's name: thevon Neumann architecture .This machine as a model of computation is now called the "Universal Turing machine".

**Introduction**Every Turing machine computes a certain fixed partial

computable function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, we can encode the action table of any Turing machine in a string. Thus we can construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and computes the tape that the encoded Turing machine would have computed. Turing described such a construction in some detail in his 1936 paper.In 1947, Turing said:

It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.

**tored-program computer**Davis (

2000 ) 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 influencedJohn von Neumann 's conception of the first discrete-symbol (as opposed to analog) computer -- theEDVAC . Davis quotes "Time" magazine to this effect, that "everyone who taps at a keyboard... is working on an incarnation of a Turing machine," and that "John von Neumann [built] on the work of Alan Turing" (Davis (2000) p. 193 quoting "Time" magazine (29 March ,1999 )).Davis makes a case that Turing's

Automatic Computing Engine (ACE) computer "anticipated" the notions of microprogamming (microcode ) andRISC processors (cf p. 188)).Knuth (1973 ,1968 ) cites Turing's work on the ACE computer as designing "hardware to facilitate subroutine linkeage" (p. 225); Davis (2000) also references this work as Turing's use of a hardware "stack" (cf footnote 18 page 237).As the Turing Machine was encouraging the construction of

computers , the UTM was encouraging the development of the fledglingcomputer science s. An early, if not the very first, assembler was proposed "by a young hot-shot programmer" for the EDVAC (Davis 2000, p. 192). Von Neumann's "first serious program ... [was] to simply sort data efficiently" (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 (in particular: Burks, Goldstine, von Neumann (1946 ), "Preliminary discussion of the logical design of an electronic computing instrument", reprinted in Bell and Newell 1971). Knuth furthermore states that:"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 in 1946 ... Turing took part in this development also; interpretive systems for the Pilot ACE computer were written under his direction" (Knuth p. 226).Davis (2000) briefly mentions operating systems and compilers as outcomes of the notion of program-as-data (p. 185).

Some, however, might raise issues with this assessment. At the time (mid-1940's to mid-1950's) a relatively small cadre of researchers were intimately involved with the architecture of the new "digital computers". Wang (

1954 ), a young researcher at this time, made the following observation::Turing's theory of computable functions antedated but has not much influenced the extensive actual construction of digital computers. These two aspects of theory and practice have been developed almost entirely independently of each other. The main reason is undoubtedly that logicians are interested in questions radically different from those with which the applied mathematicians and electrical engineers are primarily concerned. It cannot, however, fail to strike one as rather strange that often the same concepts are expressed by very different terms in the two developments." (Wang (1954 ,1957 ), p. 63)Wang hoped that his paper would "connect the two approaches." Indeed, Minsky (

1967 ) confirms this: "that the first formulation of Turing-machine theory in computer-like models appears in Wang (1957 )" (Minsky p. 200). Minsky goes on to demonstrateTuring equivalence of acounter machine .With respect to the reduction of computers to simple

Turing equivalent models (and vice versa), Wang 's (1957) title of "the first" is open to debate. While both Minsky's paper of 1961 and Wang's paper of 1957 are cited by Shepherdson and Sturgis (1963 ), they also cite and summarize in some detail the work of European mathematicians Kaphenst (1959 ), Ershov (1959), and Péter (1958 ). The names of mathematicians Hermes (1954 ,1955 ,1961 ) and Kaphenst (1959) appear in the bibliographies of both Sheperdson-Sturgis (1963 ) and Elgot-Robinson (1961 ). Two other names of importance are Canadian researchers Melzak (1961) and Lambek (1961). For much more seeTuring machine equivalents ; references can be found atRegister machine .**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 , meaning that the function in question cannot be calculated mechanically. For instance, the problem of determining whether any particular Turing machine will halt on a particular input, or on all inputs, known as theHalting problem , was shown to be, in general, undecidable in Turing's original paper.Rice's theorem shows that any non-trivial question about the behaviour or output of a Turing machine is undecidable.A universal Turing machine can calculate any

recursive function , decide anyrecursive language , and accept anyrecursively enumerable language . According to theChurch-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 calledTuring complete .An abstract version of the universal Turing machine is the

universal function , a computable function which can be used to calculate any other computable function. Theutm theorem proves the existence of such a function.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 which can be calculated. Claude Shannon first explicitly posed the question of finding the smallest possible universal Turing machine when in 1956 he showed that two symbols were sufficient, so long as enough states were used. Shannon himself proved that it was always possible to exchange states by symbols.

After some time, the smallest known universal Turing machine was due to Marvin Minsky who in 1962 discovered a 7-state 4-symbol universal Turing machine using 2-tag systems. Applying Shannon's result to Minsky's UTM upon conversion to a 2-symbol machine Minsky machine would require 43 states.

Other smaller universal Turing machines have since been found. If we denote by (m,n) the class of UTMs with m states and n symbols the following tuples were found by Yurii Rogozhin in 1996: (24, 2), (10, 3), (7, 4), (5, 5), (4, 6), (3, 10), and (2, 18). In 1985, Stephen Wolfram conjectured a 2-state 5-symbol universal Turing machine. This conjectured was proved by

Matthew Cook working as a research assistant to Stephen Wolfram. The model, also known asRule 110 Elementary Cellular Automaton had, at the time, the smallest product (2,5)=10 of any known universal Turing machine. According to Wolfram other smaller UTMs should exist and he proposed a 2-state 3-symbol Turing Machine as a candidate. On Oct 24, 2007, Wolfram announced the Turing equivalence of the system had been proven by Alex Smith -- an undergraduate studying electronic and computer engineering at theUniversity of Birmingham -- responding to a contest established by Wolfram. [*http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html*] However, on2007-10-29 Vaughan Pratt ofStanford University announced that he discovered a flaw in the proof. [*http://cs.nyu.edu/pipermail/fom/2007-October/012156.html*] Wolfram Research disputes Pratt's interpretation. [*http://forum.wolframscience.com/showthread.php?s=&threadid=1472*]**Example of universal-machine coding**:"For those who would undertake the challenge of designing a UTM exactly as Turing specified see the article in Copeland (2004) written by Davies (pp. 103ff). Davies corrects the errors in the original and shows what a sample run would look like. He claims to have successfully run a (somewhat simplified) simulation."

The following example is taken from Turing (1936). For more about this example see the page

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 "m-configuration" (instruction, state) is represented by "D" followed by a unary string of A's, i.e. "q3" = DAAA. In a similar manner he encodes the symbols blank as "D", the symbol "0" is "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:

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

:

**;**DADDCRDAA**;**DAADDRDAAA**;**DAAADDCCRDAAAA**;**DAAAADDRDAThis 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)::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-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::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.

A number of other commentators (notably Penrose 1990) provide examples of ways to encode instructions for the Universal machine. As does Penrose, most commentators use only binary symbols i.e. only symbols { 0, 1 }. Penrose goes further and writes out his entire U-machine code (pages 71-73 -- 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. For readers interested in simpler encodings for the

Post-Turing machine the discussion of Davis in (Steen, 1980, p.251ff) may be useful.**References***Citation

first = George | last = Boolos | author-link = George Boolos

first2 = John | last2 = Burgess

first3 = Richard | last3 = Jeffrey | author3-link = Richard Jeffrey

title = Computability and Logic

edition = 4th

year = 2002

place = Cambridge UK

publisher =Cambridge University Press

id = ISBN 0-521-00758-5 (pb.)*Citation

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*Citation

last = Davis | first = Martin | author-link = Martin Davis

title = Computability and Unsolvability

year = 1958

place = New York NY

publisher = McGraw-Hill Book Company . On pages 12-20 he gives examples of 5-tuple tables for Addition, The Successor Function, Subtraction (x > = y), Proper Subtraction (0 if x < y), The Identity Function and various identity functions, and Multiplication.

*Citation

editor-first = Martin | editor-last = Davis | editor-link = Martin Davis

title = The Undecidable

year = 1965

place = Hewlett NY

publisher = Raven Press*Citation

editor-first = Lynn Arthur | editor-last = Steen | editor-link = Lynn Arthur Steen

first = Martin | last = Davis | author-link = Martin Davis

contribution = What is Computation?

title = Mathematics Today: Twelve Informal Essays

year = 1980

place = New York NY

publisher = Vintage Books (Random House)

id = ISBN 978-0394745039 .*Citation

first = Martin | last = Davis | author-link = Martin Davis

title = Engines of Logic: Mathematicians and the origin of the Computer

edition = 1st

year = 2000

place = New York NY

publisher = W. W. Norton & Company

id = ISBN 0-393-32229-7 (pb.)*Citation

first = Rolf | last = Herken | author-link = Rolf Herken

title = The Universal Turing Machine – A Half-Century Survey

year =

place =

publisher =Springer Verlag

isbn = 3-211-82637-8*Citation

first = Stephen | last = Kleene | author-link = Stephen Kleene

title = Introduction to Metamathematics

year = 1952

place = Amsterdam Netherlands

publisher = North-Holland Publishing Company , 10th impression (with corrections of 6th reprint 1971). Graduate level text; most of Chapter XIII "Computable functions" is on Turing machine proofs of computability of recursive functions, etc.*Citation

first = Marvin | last = Minsky | author-link = Marvin Minsky

contribution = Size and Structure of Universal Turing Machines using Tag Systems, Recursive Function Theory

journal = Proc. Symp. Pure Mathematics

year = 1962

pages = 229-238

place = Providence RI

publisher = American Mathematical Society

volume = 5*Citation

first = Roger | last = Penrose | author-link = Roger Penrose

title =The Emperor's New Mind

year = 1999

place = Oxford UK

publisher =Oxford University Press

id = ISBN 0-19-286198-0 (pb.)*Citation

first = Emil | last = Post | author-link = Emil Post

contribution = Finite Combinatory Processes - Formulation 1

journal = Journal of Symbolic Logic

volume = 1

year = 1936

pages = 103-105 . Reprinted in "The Undecidable" pp.289ff.*Citation

first = Emil | last = Post | author-link = Emil Post

contribution = Recursive Unsolvability of a Problem of Thue

journal = Journal of Symbolic Logic

year = 1947

pages = 1-11

volume = 12 . Reprinted in "The Undecidable" pp.293ff. In the Appendix of this paper Post comments on and gives corrections to Harv | Turing | 1936 .*Citation

first = Yurii | last = Rogozhin | author-link = Yurii Rogozhin

contribution = A Universal Turing Machine with 22 States and 2 Symbols

contribution-url = http://web.archive.org/web/20050308141040/http://www.imt.ro/Romjist/Volum1/Vol1_3/turing.htm

journal = Romanian Journal Of Information Science and Technology

year = 1998

volume = 1

number = 3

pages = 259-265 . (surveys known results about small universal Turing machines)*Citation

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*Citation

first = Alan | last = Turing | author-link = Alan Turing

contribution = On Computable Numbers, With an Application to the Entscheidungsproblem

contribution-url = http://www.abelard.org/turpap2/tp2-ie.asp

journal = Proceedings of the London Mathematical Society

year = 1936

volume = 42 | issue = 2 (and Citation

last = Turing | first = A.M. | publication-date = 1937

title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction

periodical = Proceedings of the London Mathematical Society | series = 2

volume = 43 | pages = 544-6 ). Reprinted in "The Undecidable" pp.115-154.*Citation

first = Stephen | last = Wolfram | author-link = Stephen Wolfram

title = A New Kind of Science

year = 2002

pages = 706-714

publisher =Wolfram Research

url = http://www.wolframscience.com/nksonline/toc.html

isbn = 1-57955-008-8

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**universal Turing machine**— universlioji Turing o mašina statusas T sritis automatika atitikmenys: angl. universal Turing machine vok. universelle Turingmaschine, f rus. универсальная машина Тьюринга, f pranc. machine universelle de Turing, f ryšiai: sinonimas –… … Automatikos terminų žodynas**universal Turing machine**— noun A Turing machine capable of simulating the behavior of any Turing machine. See Also: Turing machine, Turing complete, Turing function … Wiktionary**Turing machine equivalents**— Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia**Turing machine**— For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… … Wikipedia**Turing machine**— noun An abstract computing machine introduced in 1936 by Alan Turing to give a mathematically precise definition of computability. See Also: universal Turing machine, Turing complete, Turing function … Wiktionary**Turing machine examples**— The following are examples to supplement the article Turing machine.Turing s very first exampleThe following table is Turing s very first example (Turing 1936):: 1. A machine can be constructed to compute the sequence 0 1 0 1 0 1... ( Undecidable … Wikipedia**Turing machine**— /toor ing, tyoor /, Math. a hypothetical device with a set of logical rules of computation: the concept is used in mathematical studies of the computability of numbers and in the mathematical theories of automata and computers. [after Alan M.… … Universalium**Probabilistic Turing machine**— Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia**Alternating Turing machine**— In computational complexity theory, an alternating Turing machine (ATM) is a non deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co NP.… … Wikipedia**Non-deterministic Turing machine**— Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… … Wikipedia