- 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: <qi, si, sk, M, qj >. qi is the state the machine is in at the first moment, si is the symbol it reads on the square, sk a symbol with which it replaces it, M is the instruction to move one square right or left or remain where it is, and qj 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.