Turing machine

The Turing Machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. The concept is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.

See also

• Langton's ant, a simple two-dimensional analogue of the Turing machine.
• Probabilistic Turing machine
• Church-Turing thesis, which says Turing machines can perform any computation that can be performed.
• Busy Beaver
• Computability logic
• Turing completeness
• Turing tarpit, any computing system or language which, like the Turing machine, is not only Turing-complete but also useless for practical computing.
• Neal Stephenson's Cryptonomicon