Universal Turing Machines
As Turing wrote in Undecidable, p. 128 (italics added):
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. 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.
Turing's paper ... contains, in essence, the invention of the modern computer and some of the programming techniques that accompanied it. —Minsky (1967), p. 104In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic 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)
Read more about this topic: Turing Machine
Famous quotes containing the words universal and/or machines:
“I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.”
—George Gordon Noel Byron (1788–1824)
“The machine has had a pernicious effect upon virtue, pity, and love, and young men used to machines which induce inertia, and fear, are near impotents.”
—Edward Dahlberg (1900–1977)