A model of computation revision notes

Structure of a Turing machine

A Turing machine can be viewed as a computer with one fixed program. The program is represented by a finite set of states and the transitions between them. The machine also has a finite alphabet of symbols, an infinite tape divided into marked-off squares, and a sensing read-write head. The head examines one square at a time, can replace the symbol in that square, and travels along the tape one square at a time. In the A-level questions described here, the tape is infinite in one direction.

One state is designated as the start state. A state with no outgoing transitions is a halting state. When the machine reaches a halting state, no further transition is available.

Transition rules

A transition rule specifies what happens for a particular current state and scanned symbol. It identifies the next state, the symbol to write, and the direction in which the head moves. A rule can be written in a transition-function form such as:

δ(q0, 1) = (q0, 1, R)

This means: if the machine is in state q0 and reads 1, it remains in q0, writes 1, and moves the head one square to the right. A state transition diagram represents the same information graphically: an arrow leaves the current state and points to the next state, with a label showing the symbol read, the symbol written and the movement.

The transition function and the diagram are two representations of the same transition rules. When tracing a machine, use the current state and the symbol under the head to select exactly one applicable rule.

Worked trace

Consider a machine with start state q0 and halting state halt. Suppose its relevant rules are:

• δ(q0, 1) = (q0, 1, R)
• δ(q0, blank) = (halt, blank, R)

If the tape initially contains 111 followed by blank squares, the head starts on the first 1 in state q0. It reads the first 1, leaves it unchanged, moves right and stays in q0. The same happens for the second and third 1. On the next square it reads blank, changes to halt, and stops. The machine has therefore scanned the consecutive 1 symbols and halted when it reached the first blank.

Why Turing machines matter

Turing machines provide a general, formal model of computation. They give a precise way to describe a computation as a sequence of state changes, tape operations and head movements. They also provide a definition of what is computable. A Universal Turing machine is important because it provides a general computational model that can represent and carry out the behaviour of other Turing machines, rather than being restricted to one particular fixed computation.

Common errors

• Confusing the current state with the symbol currently under the head.
• Forgetting that the head writes before moving according to the transition rule.
• Treating a halting state as if it must have an outgoing transition.
• Moving the head more than one square for a single transition.
• Assuming that a state diagram and a transition function describe different programs; they are alternative representations of the same rules.
• Continuing a trace after the machine has entered a halting state.