(definition)
Definition: A model of computation consisting of a finite state machine controller, a read-write head, and an unbounded sequential tape. Depending on the current state and symbol read on the tape, the machine can change its state and move the head to the left or right. Unless otherwise specified, a Turing machine is deterministic.
See also other models: cell probe model, random access machine, pointer machine, multiprocessor model, related terms: big-O notation, busy beaver, variants: alternating Turing machine, nondeterministic Turing machine, oracle Turing machine, probabilistic Turing machine, universal Turing machine.
Note: From Algorithms and Theory of Computation Handbook, page 24-19, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRC-A
An article in the Stanford Encyclopedia of Philosophy.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 21 November 2005.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Turing machine", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 21 November 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/turingMachine.html