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