Difference between revisions of "Universal Turing machine"
Karl Jones (Talk | contribs) (→See also) |
Karl Jones (Talk | contribs) (→External links) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 17: | Line 17: | ||
== See also == | == See also == | ||
| + | * [[Abstract machine]] | ||
* [[Algorithm]] | * [[Algorithm]] | ||
* [[Computer science]] | * [[Computer science]] | ||
| Line 32: | Line 33: | ||
* [https://en.wikipedia.org/wiki/Universal_Turing_machine Universal Turing machine] @ Wikipedia | * [https://en.wikipedia.org/wiki/Universal_Turing_machine Universal Turing machine] @ Wikipedia | ||
| + | |||
| + | [[Category:Computation]] | ||
| + | [[Category:Computer science]] | ||
| + | [[Category:Mathematics]] | ||
| + | [[Category:Paradox]] | ||
| + | [[Category:Turing machines]] | ||
Latest revision as of 15:52, 20 April 2016
In computer science, a Universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input.
Description
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.
Computational complexity
In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates.
See also
- Abstract machine
- Algorithm
- Computer science
- Computation
- Computational complexity
- Input (computing)
- John von Neumann
- Mathematical model
- Output (computing)
- Turing, Alan
- Turing machine
- Von Neumann architecture
External links
- Universal Turing machine @ Wikipedia
