This site is supported by donations to The OEIS Foundation.
Turing machines
There are no approved revisions of this page, so it may not have been
A Turing machine (TM) is a theoretical computing machine conceived by Alan Turing in 1937 representing an idealized model for a given mathematical calculation.
The machine has a finite number n of (active) states q, often labelled A, B, ..., and operates on an infinite tape on which each location holds one of k distinct symbols s. At each move or step, the machine reads the symbol written on the tape at its current position, and then, depending on the read symbol s and its current state q,
- overwrites the read symbol s with a given new (possibly the same) symbol s+,
- possibly shifts its position to the left or to the right on the tape, coded by d+ ∈ { LEFT (-1), RIGHT (+1) or NONE (0) },
- switches to a new (possibly the same) active state q+, or the HALT state which terminates its operation.
The machine is therefore specified by its transition table that defines the action (s+, d+, q+) as function of (q, s). For each of the n × k possibilities for (q, s), there are k × D × (n + 1) possibilities for (s+, d+, q+), with D = 2 or 3 depending on whether d+ = 0 (NONE) is allowed. Therefore, there is a theoretical total of
- (D k (n + 1))k n
Turing machines of type (n, k, D). However, not all of these will exhibit a distinct behaviour. Not only when started in state A on a blank (all '0's) tape, which is the usual initial condition, but even given any arbitrary configuration, distinct machines may show exactly the same behaviour. (For example, if two distinct states specify the same action (s+, d+, q+) for all possible inputs (q, s), then the labels of these states may obviously be permuted and still yield equivalent Turing machines.)
It is in general undecidable whether a given Turing machine will ever HALT or not. See the Busy Beaver problem for more on this.
See also
External links
- Weisstein, Eric W., Turing Machine, from MathWorld—A Wolfram Web Resource.
- Welcome — Association for Computing Machinery.
