Contents > Abstract Machines > Turing Machine

Definition

A Turing machine consists of a tape drive coupled to a state machine. Mounted onto the drive is an infinitely long tape that stores an endless sequence of characters, t, all of which are initially zero:

ti∈(−∞, ∞) ← 0

A process writes an input string to the tape at index 0:

ti∈[0,L−1] ← ith character of an input string of length L

Afterwards, the drive’s read/write head—which is limited to accessing a single character at any time—is repositioned over the first character of the input string, t0. On command, the head can step left from some ti to ti−1, or right from some ti to ti+1.

A process initializes the state machine to a starting state. At runtime, if the state machine transitions to a halt state, then the algorithm finished. At that point, the process may read output strings deposited on the tape by the algorithm.

During each processing cycle, the machine reads the character under the head, r, it pairs the character with the current state, s, and it uses the pair to perform a lookup in a state-transition table that contains a finite number of entries of the form:

[ r, s ] ↦ [ w, d, z ]

The looked-up value is a triplet representing instructions, which the machine carries out:

1. Write character w, overwriting r.
2. Step the head in direction d, repositioning it over an immediate neighbor.
3. Transition to state z.