---------------------------------------------------------------------------------------
.
---------------------------------------------------------------------------------------
#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
Machine
* Turing machine equivalents
* Turing machine examples
* Turing machine gallery
Variants
* 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
Science
* 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]
[ ]
Contents
* 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
Introduction[edit]
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
paper:
"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
machine.
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
undecidable.
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.
Efficiency[edit]
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
q3 blank P1 R q4 DAAA D DCC R DAAAA DAAADDCCRDAAAA
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.:
;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):
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. ;
zD.A.AxD.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 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
Descriptor.^[11]^[12]
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
References[edit]
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
article.
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.
Implementation
*
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,
doi:10.3233/FI-2009-0036
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,
doi:10.1016/S0304-3975(96)00077-1
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,
doi:10.1112/plms/s2-43.6.544)
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
"https://en.wikipedia.org/w/index.php?title=Universal_Turing_machine&ol
did=1101479407"
Categories:
* 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
Namespaces
* Article
* Talk
[ ] English
Views
* Read
* Edit
* View history
[ ] More
Search
____________________ Search Go
Navigation
* Main page
* Contents
* Current events
* Random article
* About Wikipedia
* Contact us
* Donate
Contribute
* Help
* Learn to edit
* Community portal
* Recent changes
* Upload file
Tools
* What links here
* Related changes
* Upload file
* Special pages
* Permanent link
* Page information
* Cite this page
* Wikidata item
Print/export
* Download as PDF
* Printable version
Languages
* 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
---------------------------------------------------------------------------------------