Turing machine

A mathematical device used by the English mathematician Alan Turing (1912–54) to make precise the notion of an algorithm, or an effective computation. A Turing machine is a computer with a potentially infinite linear tape in both directions, divided into discrete squares that are scanned one at a time. Symbols in the squares are from a finite alphabet. The instructions for the machine are sets of ordered quintuples: <q_i, s_i, s_k, M, q_j >. q_i is the state the machine is in at the first moment, s_i is the symbol it reads on the square, s_k a symbol with which it replaces it, M is the instruction to move one square right or left or remain where it is, and q_j the state at the next moment. A function f(x ) is Turing computable if, when some representation of the argument x is put on the tape, the machine halts on a representation of the value f(x ). The class of Turing computable functions is identical with the class of general recursive functions (see also Church's thesis ).