In theoretical computer science, a Turing machine is a model of computation, where an abstract machine operates on an infinite strip of tape divided into discrete cells. Turing machines can do everything that a real computer can do — problems that it cannot do are “beyond the theoretical limits of computation”.1 They’re like finite state automata with unlimited/unrestricted memory.
Deterministic Turing machines (DTM) have a few key properties: a finite state control, read-write head, and a tape with an infinite sequence of tape squares. DTM programs have a finite set of tape symbols, a finite set of states.
Footnotes
-
From Introduction to the Theory of Computation, by Michael Sipser. ↩