Turing Machines

Tape, head, and transition function: computation one step at a time.

The idea

A Turing machine is the standard formal model of computation: it makes "algorithm" a precise mathematical object, so we can prove what computation can and cannot do.

The machine works on an unbounded tape ruled into cells, one symbol per cell, with a head that reads and writes a single cell, and it carries a state drawn from a finite set — its only memory apart from the tape. At each step, the current state and the symbol under the head determine the symbol written into that cell, whether the head moves one cell left or right, and the next state.

Formally, a Turing machine is a $7$-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$: a finite state set $Q$, an input alphabet $\Sigma$, a tape alphabet $\Gamma$ containing a blank symbol $\sqcup$, and a transition function

$\delta \colon Q \times \Gamma \to Q \times \Gamma \times \{L, R\}.$

The left side is everything the machine can see in one step; the right side is everything it may do.

Run on an input string, the machine steps until it enters $q_{\text{accept}}$ or $q_{\text{reject}}$, and the set of strings it accepts is its language $L(M)$. The machine and its language are different objects: the machine is a finite program, while its language may be an infinite set of strings. The tape distinguishes the model from a finite automaton: a Turing machine writes and later rereads what it wrote, so the tape serves as unbounded memory. Nothing in the rules forces a run to end: a machine whose transitions never reach a halting state simply runs forever.

Ways to work on it

• Walkthrough. The model, what one transition can change, and tracing a run to acceptance.
• Practice. Trace a short run and count its steps to acceptance.
• Hardest. Trace a machine that writes as it runs: final tape contents, step count, and which halting state.

Not sure where to start? Take the ten-question placement test.