- 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 ).

*Philosophy dictionary.
Academic.
2011.*