Turing machine

n. A Turing machine is an abstract, mathematically well-defined finite state machine described by the British mathematician Alan M. Turing in 1937. Basically, it consists of (a) an infinitely extensible tape divided into cells marked by a symbol of a finite alphabet or a blank symbol, (b) a head performing reading and writing operations on the tape, and (c) a transition function. Given the current state of the machine and the symbol under the head, the transition function tells the machine (i) the next state it should go to, (ii) the next symbol it should write, and (iii) the direction in which the tape should move. The tape moves back and forth under the head one (and only one) cell at a time. Following Turing's idea, researchers in cognitive science and artificial intelligence have envisioned that the human mind itself may be represented as a Turing machine. – AK