A Turing machine is a theoretical computing machine invented by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine consists of a line of cells known as a "tape" that can be moved back and forth, an active element known as the "head" that possesses a property known as "state" and that can change the property known as "color" of the active cell underneath it, and a set of instructions for how the head should modify the active cell and move the tape (Wolfram 2002, pp. 78-81). At each step, the machine may modify the color of the active cell and change the state of the head. After this, it moves the tape one unit to the left or right.
Turing machines are implemented in the Wolfram Language as TuringMachine.
A generalization of the Turing machine in which the head is allowed to move 
steps in either direction was considered
by Macura (2005).
A template for specifying a 3-state, 2-color Turing machine is shown above using a form of notation due to Wolfram (2002). In this figure, a state is represented by a square containing a pointer indicating any of three possible directions; the property of 'color' is represented by the color of the square; and an instruction is represented by two squares in a column, with the top one representing a possible color and state of the active cell and the bottom one giving the new state and color of the active cell together with the direction the tape should be moved. The special state 0 (with no pointer) indicates a state at which the Turing machine should halt, i.e., cease computation.
The number of 
-state,
-color Turing machines (disallowing machines
with halting states) is given by 
(Wolfram 2002, p. 888).
An example 3-state, 2-color Turing machine is illustrated above (Wolfram 2002, p. 78). It has a total
of 
rules, which describe the machine
behavior for all possible states. In general, an 
-state, 
-color Turing machine requires 
rules to specify its behavior. Although any number
of these rules may specify a halting condition, the most commonly considered Turing
machines have either 0 or 1 halting states.
A Turing machine can run forever, enter a loop, or reach a particular state or set of conditions (i.e., the head will ever reach a given position, a given pattern will
be produced on the tape, etc.) at which it is prescribed to halt. Determining whether
a Turing machine will ever halt for a given input and set of rules is called the
halting problem. An 
-state, 2-symbol Turing machine which begins with a blank tape
and writes as many 1s as possible before reaching a halt state is known as a busy
beaver. For an 
-state
binary Turing machine, the number of 1s written for a busy
beaver is denoted 
.
Similarly, the maximum number of steps a 2-color 
-state Turing machine can take before halting is denoted 
.
Two-dimensional Turing machines are most commonly known as turmites (although the terms "ant" and "vant" are sometimes used) on square grids, and as "bees," "worms," or "turtles" on hexagonal grids. The best known turmite on a square grid is Langton's ant.
See also
Abstract Machine, Automata Theory, Automatic Set, Busy Beaver, Cellular Automaton, Chaitin's Constant, Church-Turing Thesis, Computable Number, Deterministic, Halting Problem, Langton's Ant, Mobile Automaton, Nondeterministic Turing Machine, Register Machine, Turmite, Universal Turing Machine Explore this topic in the MathWorld classroom
Explore with Wolfram|Alpha
References
Davis, M. Computability and Unsolvability. New York: Dover 1982.Itô, K. (Ed.).
"Turing Machines." §31B in Encyclopedic
Dictionary of Mathematics, 2nd ed., Vol. 1. Cambridge, MA: MIT Press,
pp. 136-137, 1987.Kleene, S. C. Introduction
to Metamathematics. Princeton, NJ: Van Nostrand, 1964.Lin, S.
and Rado, T. "Computer Studies of Turing Machine Problems." J. ACM 12,
196-212, 1965.Macura, W. K. "
-Skip Turing Machines." Complex Systems 15,
237-244, 2005.Ord, T. "Hypercomputation: Computing More Than the
Turing Machine." 25 Sep 2002. http://arxiv.org/abs/math.LO/0209332.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. Reprinted in The
Undecidable (Ed. M. David). Hewlett, NY: Raven Press, 1965.Turing,
A. M. "Correction to: On Computable Numbers, with an Application to the
Entscheidungsproblem." Proc. London Math. Soc. Ser. 2 43, 544-546,
1938.Wolfram, S. A
New Kind of Science. Champaign, IL: Wolfram Media, pp. 78-81,
888-889, 1110, 1119,
and 1128, 2002.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Turing Machine." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TuringMachine.html