en.wikipedia.org, 2022-08-17 | Main page
Saved from web.archive.org, with Lynx.
   #alternate Edit this page Wikipedia (en)

Universal Turing machine

   From Wikipedia, the free encyclopedia
   Jump to navigation Jump to search
   Type of Turing machine
   "Universal machine" redirects here. For other uses, see Universal
   machine (disambiguation).

          Turing machines
     * Turing machine equivalents
     * Turing machine examples
     * Turing machine gallery

     * Alternating Turing machine
     * Neural Turing machine
     * Nondeterministic Turing machine
     * Quantum Turing machine
     * Post-Turing machine
     * Probabilistic Turing machine
     * Multitape Turing machine
     * Multi-track Turing machine
     * Symmetric Turing machine
     * Total Turing machine
     * Unambiguous Turing machine
     * Universal Turing machine
     * Zeno machine

     * Alan Turing
     * Category:Turing machine

     * v
     * t
     * e

   In computer science, a universal Turing machine (UTM) is a Turing
   machine that can simulate an arbitrary Turing machine on arbitrary
   input. The universal machine essentially achieves this by reading both
   the description of the machine to be simulated as well as the input to
   that machine from its own tape. Alan Turing introduced the idea of such
   a machine in 1936-1937. This principle is considered to be the origin
   of the idea of a stored-program computer used by John von Neumann in
   1946 for the "Electronic Computing Instrument" that now bears von
   Neumann's name: the von Neumann architecture.^[1]

   In terms of computational complexity, a multi-tape universal Turing
   machine need only be slower by logarithmic factor compared to the
   machines it simulates.^[2]
   [ ]


     * 1 Introduction
     * 2 Stored-program computer
     * 3 Mathematical theory
     * 4 Efficiency
     * 5 Smallest machines
     * 6 Machines with no internal states
     * 7 Example of universal-machine coding
     * 8 Programming Turing machines
     * 9 See also
     * 10 References
     * 11 External links


   Universal Turing machine.svg

   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 complete detail in his 1936

          "It is possible to invent a single machine which can be used to
          compute any computable sequence. If this machine U is supplied
          with a tape on the beginning of which is written the S.D
          ["standard description" of an action table] of some computing
          machine M, then U will compute the same sequence as M."^[3]

Stored-program computer[edit]

   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... is working on an incarnation of a Turing
   machine," and that "John von Neumann [built] on the work of Alan
   Turing" (Davis 2000: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 (Davis 2000:188). Knuth cites Turing's work on the ACE
   computer as designing "hardware to facilitate subroutine linkage"
   (Knuth 1973:225); Davis also references this work as Turing's use of a
   hardware "stack" (Davis 2000:237 footnote 18).

   As the Turing Machine was encouraging the construction of computers,
   the UTM was encouraging the development of the fledgling computer
   sciences. An early, if not the very first, assembler was proposed "by a
   young hot-shot programmer" for the EDVAC (Davis 2000:192). Von
   Neumann's "first serious program ... [was] to simply sort data
   efficiently" (Davis 2000:184). Knuth observes that the subroutine
   return embedded in the program itself rather than in special registers
   is attributable to von Neumann and Goldstine.^[4] 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 1973:226).

   Davis briefly mentions operating systems and compilers as outcomes of
   the notion of program-as-data (Davis 2000:185).

   Some, however, might raise issues with this assessment. At the time
   (mid-1940s to mid-1950s) a relatively small cadre of researchers were
   intimately involved with the architecture of the new "digital
   computers". Hao 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:63)

   Wang hoped that his paper would "connect the two approaches." Indeed,
   Minsky confirms this: "that the first formulation of Turing-machine
   theory in computer-like models appears in Wang (1957)" (Minsky
   1967:200). Minsky goes on to demonstrate Turing equivalence of a
   counter machine.

   With respect to the reduction of computers to simple Turing equivalent
   models (and vice versa), Minsky's designation of Wang as having made
   "the first formulation" 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 Peter
   (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 see
   Turing machine equivalents; references can be found at register

Mathematical theory[edit]

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

   A universal Turing machine can calculate any 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 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.


   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 Goedel number and computational
   equivalence between Turing machines and m-recursive functions.
   Similarly, our construction associates to every binary string a, a
   Turing machine M[a].

   Starting from the above encoding, in 1966 F. C. Hennie and R. E.
   Stearns showed that given a Turing machine M[a] that halts on input x
   within N steps, then there exists a multi-tape universal Turing machine
   that halts on inputs a, 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: <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle
   displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD">
   <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic"
   mathvariant="script">O</mi> </mrow> </mrow> <mrow> <mo>(</mo> <mrow>
   <mi>N</mi> <mi>log</mi> <mo>⁡</mo> <mrow
   class="MJX-TeXAtom-ORD"> <mi>N</mi> </mrow> </mrow> <mo>)</mo> </mrow>
   </mstyle> </mrow> <annotation
   encoding="application/x-tex">{\displaystyle {\mathcal {O}}\left(N\log
   {N}\right)}</annotation> </semantics> :MATH]
   {\displaystyle {\mathcal {O}}\left(N\log {N}\right)} simulation, using
   Donald Knuth's Big O notation.^[5] 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: <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle
   displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD">
   <mrow class="MJX-TeXAtom-ORD"> <mi class="MJX-tex-caligraphic"
   mathvariant="script">O</mi> </mrow> </mrow> <mo stretchy="false">(</mo>
   <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation
   encoding="application/x-tex">{\displaystyle {\mathcal
   {O}}(N)}</annotation> </semantics> :MATH]
   {\mathcal {O}}(N) simulation.^[6]

Smallest machines[edit]

   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 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).^[7]^[8]^[9] 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.^[10] 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[edit]

   If you allow multiple heads on the Turing machine then you can have a
   Turing machine with no internal states at all. The "states" are encoded
   as part of 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 are or if a 2-colour Universal Turing machine is
   possible with multiple heads. It also means that 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.

Example of universal-machine coding[edit]

   For those who would undertake the challenge of designing a UTM exactly
   as Turing specified see the article by Davies in Copeland (2004: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 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, 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:
   Current m-configuration Tape symbol Print-operation Tape-motion Final
   m-configuration Current m-configuration code Tape symbol code
   Print-operation code Tape-motion code Final m-configuration code
   5-tuple assembled code
   q1 blank P0 R q2 DA D DC R DAA DADDCRDAA
   q2 blank E R q3 DAA D D R DAAA DAADDRDAAA
   q4 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.:


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


   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

          ee.; .D.A.D.D.C.R.D.A.A. ;

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

   A number of other commentators (notably Penrose 1989) 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 }, or { blank, mark | }. Penrose goes further and writes out his
   entire U-machine code (Penrose 1989: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 (Steen 1980:251ff)
   may be useful.

   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.

Programming Turing machines[edit]

   Various higher level languages are designed to be compiled into a
   Turing machine. Examples include Laconic and Turing Machine

See also[edit]

     * Alternating Turing machine
     * Von Neumann universal constructor -- an attempt to build a
       self-replicating Turing machine
     * Kleene's T predicate -- a similar concept for u-recursive functions
     * Turing completeness


    1. ^ Martin Davis, The universal computer : the road from Leibniz to
       Turing (2017)
    2. ^ Arora and Barak, 2009, Theorem 1.9
    3. ^ Boldface replacing script. Turing 1936 in Davis 1965:127-128. An
       example of Turing's notion of S.D is given at the end of this
    4. ^ In particular: Burks, Goldstine, von Neumann (1946), Preliminary
       discussion of the logical design of an electronic computing
       instrument, reprinted in Bell and Newell 1971
    5. ^ Arora and Barak, 2009, Theorem 1.9
    6. ^ Arora and Barak, 2009, Exercises 4.1
    7. ^ Rogozhin, 1996
    8. ^ Kudlek and Rogozhin, 2002
    9. ^ Neary and Woods, 2009
   10. ^ Neary and Woods, 2009b
   11. ^ "Shtetl-Optimized >> Blog Archive >> The 8000th Busy Beaver
       number eludes ZF set theory: new paper by Adam Yedidia and me".
       www.scottaaronson.com. 3 May 2016. Retrieved 29 December 2016.
   12. ^ "Laconic - Esolang". esolangs.org. Retrieved 29 December 2016.

   General references

   Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern
   Approach. Cambridge University Press. ISBN 978-0-521-42426-4. "section
   1.4, "Machines as strings and the universal Turing machine" and 1.7,
   "Proof of theorem 1.9""

   Original Paper

   Turing, A. M. (1936). "On Computable Numbers, with an Application to
   the Entscheidungsproblem" (PDF).

   Seminal papers

   Hennie, F. C.; Stearns, R. E. (1966). "Two-Tape Simulation of Multitape
   Turing Machines". Journal of the ACM. 13 (4): 533.
   doi:10.1145/321356.321362. S2CID 2347143.


   Kamvysselis (Kellis), Manolis (1999). "Scheme Implementation of a
   Universal Turing Machine". Self-published.

   Formal verification

   Asperti, Andrea; Ricciotti, Wilmer (2015). "A formalization of
   multi-tape Turing machines" (PDF). Theoretical Computer Science.
   Elsevier. 603: 23-42. doi:10.1016/j.tcs.2015.07.013. ISSN 0304-3975.

   Other references

   Copeland, Jack, ed. (2004), The Essential Turing: Seminal Writings in
   Computing, Logic, Philosophy, Artificial Intelligence, and Artificial
   Life plus The Secrets of Enigma, Oxford UK: Oxford University Press,
   ISBN 0-19-825079-7

     Davis, Martin (1980), "What is Computation?", in Steen, Lynn Arthur
   (ed.), Mathematics Today: Twelve Informal Essays, New York: Vintage
   Books (Random House), ISBN 978-0-394-74503-9.

     Davis, Martin (2000), Engines of Logic: Mathematicians and the origin
   of the Computer (1st ed.), New York NY: W. W. Norton & Company,
   ISBN 0-393-32229-7, (pb.)

     Goldstine, Herman H.; von Neumann, John. Planning and Coding of the
   Problems for an Electronic Computing Instrument. Institute for Advanced
   Study (Rep. 1947 ed.). Princeton.
   Bell, C. Gordon; Newell, Allen (1971). Computer Structures: Readings
   and Examples (Reprinted ed.). New York: McGraw-Hill Book Company.
   pp. 92-119. ISBN 0-07-004357-4.

     Herken, Rolf (1995), The Universal Turing Machine - A Half-Century
   Survey, Springer Verlag, ISBN 3-211-82637-8

     Knuth, Donald E. (1973), The Art of Computer Programming,
   vol. 1/Fundamental Algorithms (second ed.), Addison-Wesley Publishing
   Company The first of Knuth's series of three texts.

     Kudlek, Manfred; Rogozhin, Yurii (2002), "A universal Turing machine
   with 3 states and 9 symbols", in Werner Kuich; Grzegorz Rozenberg; Arto
   Salomaa (eds.), Developments in Language Theory: 5th International
   Conference, DLT 2001 Wien, Austria, July 16-21, 2001, Revised Papers,
   Lecture Notes in Computer Science, vol. 2295, Springer, pp. 311-318,
   doi:10.1007/3-540-46011-x_27, ISBN 978-3-540-43453-5

     Minsky, Marvin (1962), "Size and Structure of Universal Turing
   Machines using Tag Systems, Recursive Function Theory", Proc. Symp.
   Pure Mathematics, Providence RI: American Mathematical Society, 5:
   229-238, doi:10.1090/pspum/005/0142452

     Neary, Turlough; Woods, Damien (2009), "Four Small Universal Turing
   Machines" (PDF), Fundamenta Informaticae, 91 (1): 123-144,

     Neary, Turlough; Woods, Damien (2009b), "Small Weakly Universal
   Turing Machines", 17th International Symposium on Fundamentals of
   Computation Theory, Lecture Notes in Computer Science, vol. 5699,
   Springer, pp. 262-273

     Penrose, Roger (1989), The Emperor's New Mind, Oxford UK: Oxford
   University Press, ISBN 0-19-851973-7, (hc.), (pb.)

     Rogozhin, Yurii (1996), "Small Universal Turing Machines",
   Theoretical Computer Science, 168 (2): 215-240,

     Shannon, Claude (1956), "A Universal Turing Machine with Two Internal
   States", Automata Studies, Princeton, NJ: Princeton University Press,
   pp. 157-165

     Turing, A.M. (1936), "On Computable Numbers, with an Application to
   the Entscheidungsproblem", Proceedings of the London Mathematical
   Society, 2, vol. 42, pp. 230-65, doi:10.1112/plms/s2-42.1.230

     Turing, A.M. (1938), "On Computable Numbers, with an Application to
   the Entscheidungsproblem: A correction", Proceedings of the London
   Mathematical Society, 2 (published 1937), vol. 43, no. 6, pp. 544-6,
   Davis, Martin, ed. (1965). The Undecidable (Reprint ed.). Hewlett, NY:
   Raven Press. pp. 115-154. "with corrections to Turing's UTM by Emil
   Post cf footnote 11 pg:299"

External links[edit]

   Smith, Alvy Ray. "A Business Card Universal Turing Machine" (PDF).
   Retrieved 2 January 2020.

   Authority control: National libraries Edit this at Wikidata
     * Germany

   Retrieved from

     * Turing machine

   Hidden categories:
     * Articles with short description
     * Short description is different from Wikidata
     * Use dmy dates from January 2020
     * CS1: long volume value
     * Articles with GND identifiers

Navigation menu

Personal tools

     * Not logged in
     * Talk
     * Contributions
     * Create account
     * Log in


     * Article
     * Talk

   [ ] English


     * Read
     * Edit
     * View history

   [ ] More


   ____________________ Search Go


     * Main page
     * Contents
     * Current events
     * Random article
     * About Wikipedia
     * Contact us
     * Donate


     * Help
     * Learn to edit
     * Community portal
     * Recent changes
     * Upload file


     * What links here
     * Related changes
     * Upload file
     * Special pages
     * Permanent link
     * Page information
     * Cite this page
     * Wikidata item


     * Download as PDF
     * Printable version


     * a+l+e+r+b+y+tm
     * B"lgarski
     * Catal`a
     * Deutsch
     * Ellynika'
     * Espanol
     * f+a+r+s+
     * Franc,ais
     * Hrvatski
     * Italiano
     * Mirandes
     * Nederlands
     * Portugues
     * Russkij
     * Srpski / srpski
     * Ukrayins'ka

   Edit links

     * This page was last edited on 31 July 2022, at 07:36 (UTC).
     * Text is available under the Creative Commons Attribution-ShareAlike
       License 3.0; additional terms may apply. By using this site, you
       agree to the Terms of Use and Privacy Policy. Wikipedia(R) is a
       registered trademark of the Wikimedia Foundation, Inc., a
       non-profit organization.

     * Privacy policy
     * About Wikipedia
     * Disclaimers
     * Contact Wikipedia
     * Mobile view
     * Developers
     * Statistics
     * Cookie statement

     * Wikimedia Foundation
     * Powered by MediaWiki
Saved from web.archive.org, with Lynx.
Main page
© 2022 Matei. No cookies®