Finite automata have constant memory, pushdown automata a memory accessible only from the top. The Turing machine removes these restrictions: it has an unbounded tape that it can read and write at any position, moving left and right. This model is used to define what it means, mathematically, for a problem to be solvable by an algorithm. In this article I treat it as a formal object and leave the history aside.
The ingredients
A Turing machine (deterministic, single-tape) is a 7-tuple (Q, Σ, Γ, δ, q₀, q_acc, q_rej):
- Q is the finite set of states;
- Σ is the input alphabet, which does not contain the blank symbol ⊔;
- Γ is the tape alphabet, with Σ ⊆ Γ and ⊔ ∈ Γ;
- δ: Q × Γ → Q × Γ × {L, R} is the transition function;
- q₀ is the start state;
- q_acc and q_rej are the accept and reject states, distinct from each other.
The transition δ(q, a) = (r, b, R) reads: "in state q, if the head reads a, write b in place of a, move right and enter state r". L means a move to the left; if the head is already on the first cell, it stays put.
How it starts and how it stops
At the start the input w occupies the first cells of the tape, every other cell holds the blank, the head is on the first cell and the state is q₀. The machine applies δ one step at a time.
The computation stops only on entering q_acc or q_rej. There are therefore three possible outcomes:
- the machine accepts (reaches q_acc);
- the machine rejects (reaches q_rej);
- the machine never halts.
The third outcome is the big novelty compared with finite automata, which always stop after reading the input. It is precisely this possibility that makes Turing machines so powerful and, at the same time, gives rise to undecidable problems.
Configurations
To describe a computation precisely we use the configuration: a complete snapshot of the machine at one instant. It is written as the string u q v, where:
- u is the tape content to the left of the head;
- q is the current state;
- v is the content from the head position onwards (the first symbol of v is the one being read), omitting trailing blanks.
For example, 1 0 q₃ 1 1 means: tape 1011, state q₃, head on the third symbol. A computation is a sequence of configurations, each following from the previous one by applying δ. Configurations are the key to many proofs: they let us encode an entire computation as a finite string, and therefore reason about computations using other machines.
Recognizing and deciding
The language recognized by a machine M is the set of strings M accepts. On other strings M may reject or fail to halt.
A machine is a decider if it halts on every input. In that case we say it decides the language it recognizes.
This gives two fundamental classes:
- Turing-recognizable (or recursively enumerable) languages: some machine recognizes them;
- decidable (or recursive) languages: some decider exists.
Every decidable language is recognizable, but not the other way round.
A worked example: {0ⁿ1ⁿ}
Let us build a decider for {0ⁿ1ⁿ : n ≥ 0}, a language no finite automaton recognizes. The strategy is to cross off one 0 and one 1 at a time.
- If the current cell holds a blank, accept. If it holds a 1, reject. If it holds a 0, replace it with X.
- Move right, skipping 0s and Ys, to the first 1. If you find a blank before a 1, reject. Otherwise replace the 1 with Y.
- Move left to the first X and step one cell to the right.
- If you read a 0, repeat from step 1 on that cell. If you read a Y, scan right over the Ys: if you find a blank accept, if you find any other symbol reject.
Follow the input 0011:
- step 1: X011;
- step 2: X0Y1;
- return and repeat: XXY1, then XXYY;
- step 4: after the second X the head reads Y, scans the Ys and finds the blank. Accept.
With 0010 the second pass finds no 1 after the second marked 0, because it meets a 0 and then the blank: reject. In every case the machine halts, so it is a decider. The number of steps is proportional to n², because each pass crosses the tape.
Why this particular model
Tape, head and states may look like arbitrary choices. The point is that the model is robust: adding more tapes, allowing nondeterminism or making the tape infinite in both directions does not change the class of recognizable languages. And every other reasonable model of computation known computes exactly the same functions. This robustness justifies using the Turing machine as the reference definition of "algorithm".
In short
- A Turing machine has finitely many states, an unbounded tape and a head that reads, writes and moves.
- There are three possible outcomes: accept, reject or never halt.
- Configurations describe one instant of the computation as a finite string.
- Recognizing is not deciding: a decider must halt on every input.
- The model is robust under variants, which is why it serves as the definition of an algorithm.
