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 thereof from its own tape. Alan Turing introduced this machine in 1936–1937. This model is considered by some (for example, Martin Davis (2000)) to be the origin of the stored program computer—used by John von Neumann (1946) for the "Electronic Computing Instrument" that now bears von Neumann's name: the von Neumann architecture. It is also known as universal computing machine, universal machine (UM), machine U, U.
In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates.
Read more about Universal Turing Machine: Introduction, Stored-program Computer, Mathematical Theory, Efficiency, Smallest Machines, Example of Universal-machine Coding
Famous quotes containing the words universal and/or machine:
“I admit that the generation which produced Stalin, Auschwitz and Hiroshima will take some beating; but the radical and universal consciousness of the death of God is still ahead of us; perhaps we shall have to colonize the stars before it is finally borne in upon us that God is not out there.”
—R.J. Hollingdale (b. 1930)
“A multitude of little superfluous precautions engender here a population of deputies and sub-officials, each of whom acquits himself with an air of importance and a rigorous precision, which seemed to say, though everything is done with much silence, “Make way, I am one of the members of the grand machine of state.””
—Marquis De Custine (1790–1857)