Universal Turing machine (nonfiction): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[File:Universal Turing machine.svg|thumb|A Universal Turing machine '''U'''. '''U''' consists of a set of instructions in the table that can “execute” the correctly-formulated “code number” of any arbitrary Turing machine '''M''' on its tape. In some models, the head shuttles back and forth between various regions on the tape. In other models the head shuttles the tape back and forth.]]In [[computer science]], a '''Universal Turing machine''' ('''UTM''') is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. | [[File:Universal Turing machine.svg|thumb|A Universal Turing machine '''U'''. '''U''' consists of a set of instructions in the table that can “execute” the correctly-formulated “code number” of any arbitrary Turing machine '''M''' on its tape. In some models, the head shuttles back and forth between various regions on the tape. In other models the head shuttles the tape back and forth.]]In [[computer science]], a '''Universal Turing machine''' ('''UTM''') is a [[Turing machine (nonfiction)|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. | 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. | [[Alan Turing (nonfiction)|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. | 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 (nonfiction)|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. | It is also known as universal computing machine, universal machine (UM), machine U, U. | ||
In terms of [[Computational complexity (nonfiction)|computational complexity]], a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates. | In terms of [[Computational complexity (nonfiction)|computational complexity]], a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates. | ||
== | == In the News == | ||
<gallery | <gallery> | ||
File:Thought camera.jpg|link=Scrying engine|Many [[Scrying engine|scrying engines]] behave according to Universal Turing machine principles. | File:Thought camera.jpg|link=Scrying engine|Many [[Scrying engine|scrying engines]] behave according to Universal Turing machine principles. | ||
File:Alan_Turing_az_1930-as_években.jpg|link=Alan Turing (nonfiction)|[[Alan Turing (nonfiction)|Alan Turing]] conducts series of thought experiments based on universal Turing machine principles. | |||
</gallery> | </gallery> | ||
== Fiction cross-reference == | |||
* [[Gnomon algorithm]] - a mathematical function which converts computation to force. | * [[Gnomon algorithm]] - a mathematical function which converts computation to force. | ||
| Line 26: | Line 25: | ||
== Nonfiction cross-reference == | == Nonfiction cross-reference == | ||
* [[Alan Turing (nonfiction)]] | |||
* [[Algorithm (nonfiction)]] | * [[Algorithm (nonfiction)]] | ||
* [[Computational complexity (nonfiction)]] | * [[Computational complexity (nonfiction)]] | ||
* [[Computer science (nonfiction)]] | * [[Computer science (nonfiction)]] | ||
* [[Golly (program) (nonfiction)]] | |||
* [[John von Neumann (nonfiction)]] | |||
* [[Mathematics (nonfiction)]] | * [[Mathematics (nonfiction)]] | ||
* [[Turing machine (nonfiction)]] | |||
External links: | |||
* [https://en.wikipedia.org/wiki/Universal_Turing_machine Universal Turing machine] @ Wikipedia | * [https://en.wikipedia.org/wiki/Universal_Turing_machine Universal Turing machine] @ Wikipedia | ||
Latest revision as of 17:19, 18 May 2017
A Universal Turing machine U. U consists of a set of instructions in the table that can “execute” the correctly-formulated “code number” of any arbitrary Turing machine M on its tape. In some models, the head shuttles back and forth between various regions on the tape. In other models the head shuttles the tape back and forth.
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.
In the News
Many scrying engines behave according to Universal Turing machine principles.
Alan Turing conducts series of thought experiments based on universal Turing machine principles.
Fiction cross-reference
- Gnomon algorithm - a mathematical function which converts computation to force.
- Scrying engine - closely related to Universal Turing machines.
Nonfiction cross-reference
- Alan Turing (nonfiction)
- Algorithm (nonfiction)
- Computational complexity (nonfiction)
- Computer science (nonfiction)
- Golly (program) (nonfiction)
- John von Neumann (nonfiction)
- Mathematics (nonfiction)
- Turing machine (nonfiction)
External links:
- Universal Turing machine @ Wikipedia