A theoretical computing machine which consists of an infinitely long magnetic tape on which instructions can be written and erased, a finite register of memory, and a processor capable of carrying out the following instructions: move the tape right, move the tape left, change the state of the register based on its current value and a value on the tape, and write or erase a value on the tape. The machine keeps processing instructions until it reaches a particular state, causing it to halt. Determining whether a Turing machine will halt for a given input and set of rules is called the Halting Problem.

**References**

Penrose, R. ``Algorithms and Turing Machines.'' Ch. 2 in *The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics.*
Oxford, England: Oxford University Press, pp. 30-73, 1989.

Turing, A. M. ``On Computable Numbers, with an Application to the Entscheidungsproblem.'' *Proc. London
Math. Soc. Ser. 2* **42**, 230-265, 1937.

Turing, A. M. ``Correction to: On Computable Numbers, with an Application to the Entscheidungsproblem.'' *Proc. London
Math. Soc. Ser. 2* **43**, 544-546, 1938.

© 1996-9

1999-05-26