|
|
|
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.
See also Busy Beaver, Cellular Automaton, Chaitin's Omega, Church-Turing Thesis, Computable Number, Halting Problem, Universal Turing Machine
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.