Editing Turing machine (section)

==Universal Turing machines==
{{Main|Universal Turing machine}}

[[File:Model of a Turing machine.jpg|thumb|An implementation of a Turing machine]]
As Turing wrote in ''The Undecidable'', p.&nbsp;128 (italics added):
{{blockquote|It is possible to invent a ''single machine'' which can be used to compute ''any'' computable sequence. If this machine '''U''' is supplied with the tape on the beginning of which is written the string of quintuples separated by semicolons of some computing machine '''M''', then '''U''' will compute the same sequence as '''M'''.}}

This finding is now taken for granted, but at the time (1936) it was considered astonishing.{{citation needed|date=December 2021}} The model of computation that Turing called his "universal machine"—"'''U'''" for short—is considered by some (cf. Davis (2000)) to have been the fundamental theoretical breakthrough that led to the notion of the [[stored-program computer]].

{{blockquote|Turing's paper ... contains, in essence, the invention of the modern computer and some of the programming techniques that accompanied it.|Minsky (1967), p. 104}}

In terms of [[Computational complexity theory|computational complexity]], a multi-tape universal Turing machine need only be slower by [[logarithm]]ic factor compared to the machines it simulates. This result was obtained in 1966 by F. C. Hennie and [[R. E. Stearns]]. (Arora and Barak, 2009, theorem 1.9)