n. an abstract machine that provides the generally accepted model of serial computation, which, given Church's thesis, corresponds to what is recursively computable (see recursive). A deterministic Turing machine has a finite control, an indefinitely long input tape that is divided into units or cells of which a finite number contain a symbol drawn from a finite vocabulary, and a moving tape head. In each move the machine scans a tape cell, and, as determined by its present state and that symbol, overprints or deletes a non-blank symbol on the tape cell scanned, moves its head one cell to the left or right, and changes state. The machine can be fully described by a sequence of ordered quintuples: (a, 0, 1, R, b) can be read as the instruction `in state a, if the tape cell contains a 0, then replace it with a 1, move one cell right, and go into state b'. Some authors use ordered quadruples to describe the machine, regarding as separate the instructions to write and to move. Among the finite set of states is the initial state and a subset consisting of final states. The machine continues its operation until one of these states is encountered and the machine halts. The halting problem is that of determining whether a Turing machine will halt when presented with a given input string, and is one of many unsolvable problems. For a decision problem the final states may be taken to consist of yes and no and the machine is said to accept the input string if it terminates finitely with yes. To correspond to a decision procedure the machine must halt for all possible input strings. This model can be shown to be equivalent to most other formulations proposed for serial computation, and Turing proved that such a machine with only th e symbols 0 and 1 has the power of any machine devised to compute a particular algorithm. (Named after the English mathematician and logician, Alan Mathison Turing (1912-54), who built some of the earliest digital computers. His death of cyanide poisoning while conducting electrolysis experiments in connection with his work on the development of cells was claimed to be accidental, but is now generally regarded as suicide.)