Turing machine

Turing machine (TM) An imaginary computing machine defined as a mathematical abstraction by Alan Turing to make precise the notion of an effective procedure (i.e. an algorithm). There are many equivalent ways of dealing with this problem; among the first was Turing's abstract machine, published in 1936.

A Turing machine is an automaton that includes a linear tape that is potentially infinite (in both directions), divided into boxes or cells, and read by a read-head that scans one cell at a time. Symbols written on the tape are drawn from a finite alphabet: s₀,…,s_p

The control or processing unit of the machine can assume one of a finite number of distinct internal states: q₀,…,q_m

The “program” for a given machine is assumed to be made up from a finite set of instructions that are quintuples of the form q_is_js_kXq_j where X is R, L, or N

The first symbol indicates that the machine is in state q_i while the second indicates that the head is reading s_j on the tape. In this state the machine will replace s_j by s_k and if X = R the head will move to the right; if X = L it will move to the left and if X = N it will remain where it is. To complete the sequence initiated by this triple the machine will go into state q_j.

The machine calculates functions on the natural numbers as follows: a function f, f : N^k → N where N = {0,1,2,…}, N^k = N × … × N k times

is (Turing) computable if for each x in N^k, when some representation of x in N^k is placed on the tape (with the machine in the initial state of q₀ say), the machine halts with a representation of f(x) on the tape. See also effective computability.

It is customary in the study of abstract computation models to make a distinction between deterministic and nondeterministic algorithms. In a deterministic Turing machine the overall course of the computation is completely determined by the Turing machine (program), the starting state, and the initial tape-inputs; in a nondeterministic Turing machine there are several possibilities at each stage of the computation: it can execute one out of possibly several machine instructions. The class of problems solvable by deterministic Turing machines in polynomial time is the class P; the class of problems solvable by nondeterministic Turing machines in polynomial time is the class NP. See also P=NP question.