TOPICS
Search

Turing Machine


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 n steps in either direction was considered by Macura (2005).

TuringMachineRules

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 n-state, s-color Turing machines (disallowing machines with halting states) is given by (2ns)^(ns) (Wolfram 2002, p. 888).

TuringMachine

An example 3-state, 2-color Turing machine is illustrated above (Wolfram 2002, p. 78). It has a total of 3×2=6 rules, which describe the machine behavior for all possible states. In general, an n-state, k-color Turing machine requires k×n 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 n-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 n-state binary Turing machine, the number of 1s written for a busy beaver is denoted Sigma(n). Similarly, the maximum number of steps a 2-color n-state Turing machine can take before halting is denoted S(n).

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. "n-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

Turing Machine

Cite this as:

Weisstein, Eric W. "Turing Machine." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TuringMachine.html

Subject classifications