Turing Machine
A Turing Machine is an Abstract Machine that manipulates symbols on a strip of tape according to a table of rules.
- Context:
- It must have:
- a finite set of States.
- a finite Alphabet.
- a finite set of Instructions.
- an infinitely long tape of Characters.
- It can be a 5-Tuple Turing Machine or a 4-Tuple Turing Machine.
- It can range from being a Single-Tape Turing Machine to being a Multi-Tape Turing Machine.
- It can range from being a Deterministic Turing Machine to being a Non-Deterministic Turing Machine (such as a probabilistic Turing machine).
- It can range from being a Universal Turing Machine to being a ...
- It must have:
- See: Algorithm, Busy Beaver Task, Computational Complexity, Lambda Calculus, Computation, Church–Turing Thesis.
References
2014
- (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Turing_machine Retrieved:2014-9-21.
- A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
The "Turing" machine was invented in 1936 by Alan Turing [1] who called it an "a-machine" (automatic machine). The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation. Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:
...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings. [2] (Turing 1948, p. 3)
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective methods in logic and mathematics, and provide a precise definition of an algorithm or "mechanical procedure". Studying their abstract properties yields many insights into computer science and complexity theory.
- A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.
- ↑ The idea came to him in mid-1935 (perhaps, see more in the History section) after a question posed by M. H. A. Newman in his lectures: "Was there a definite method, or as Newman put it, a mechanical process which could be applied to a mathematical statement, and which would come up with the answer as to whether it was provable" (Hodges 1983:93). Turing submitted his paper on 31 May 1936 to the London Mathematical Society for its Proceedings (cf Hodges 1983:112), but it was published in early 1937 and offprints were available in February 1937 (cf Hodges 1983:129).
- ↑ See the definition of “innings” on Wiktionary
2009
- (WordNet, 2009) ⇒ http://wordnetweb.princeton.edu/perl/webwn?s=turing%20machine
- S: (n) Turing machine (a hypothetical computer with an infinitely long memory tape)
- http://en.wiktionary.org/wiki/Turing_machine
- 1. (computing theory) An abstract computing machine introduced in 1936 by Alan Turing to give a mathematically precise definition of computability.