
related topics 
{math, number, function} 
{system, computer, user} 
{theory, work, human} 
{work, book, publish} 
{mi², represent, 1st} 
{style, bgcolor, rowspan} 
{game, team, player} 

A Turing machine is a theoretical 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 described by Alan Turing in 1937,^{[1]} who called it an "a(utomatic)machine". Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. They 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 infinite 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. 61)
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 mathematicallyoriented 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 method 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.^{[3]}
Contents
Full article ▸


related documents 
Linked list 
Wikipedia:Free Online Dictionary of Computing/R  S 
C++ 
Computer numbering formats 
Forth (programming language) 
Prolog 
Spinor 
Fibonacci number 
System of linear equations 
Relational model 
Laplace transform 
Quadratic reciprocity 
Combinatory logic 
Linear programming 
ObjectiveC 
Field (mathematics) 
Trigonometric functions 
Big O notation 
Binary search algorithm 
Bernoulli number 
Distribution (mathematics) 
Redblack tree 
Mandelbrot set 
Banach–Tarski paradox 
Formal power series 
Serialization 
Lebesgue integration 
Lambda calculus 
Padic number 
Determinant 
