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.

Related Topics:
Abstract machine - 1936 - Alan Turing - Algorithm - Computer science - Complexity theory - Computation - Church-Turing thesis

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The concept of the Turing machine is based on the idea of a person executing a well-defined procedure by changing the contents of an unlimited number of ordered paper sheets that can contain one of a finite set of symbols. The person needs to remember one of a finite set of states and the procedure is formulated in very basic steps in the form of "If your state is 42 and the symbol you see is a '0' then replace this with a '1', move one symbol to the right, and assume state 17 as your new state."

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Turing machines shouldn't be confused with the Turing test,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Turing's attempt to capture the notion of artificial intelligence.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine or simply a universal machine as Turing described it in 1947:It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~