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:
“To revolutionize, at one effort, the universal world of human thought, human opinion, and human sentiment.... All that he has to do is to write and publish a very little book. Its title should be simple—a few plain words—”My Heart Laid Bare.” But—this little book must be true to its title.”
—Edgar Allan Poe (1809–1849)
“The American people is out to get the kaiser. We are bending every nerve and every energy towards that end; anybody who gets in the way of the great machine the energy and devotion of a hundred million patriots is building towards the stainless purpose of saving civilization from the Huns will be mashed like a fly. I’m surprised that a collegebred man like you hasn’t more sense. Don’t monkey with the buzzsaw.”
—John Dos Passos (1896–1970)