Tools · AQA A Level 3.2
Define states, a transition function and an input tape. Step through execution one move at a time or run to completion. Three built-in examples: 0ⁿ1ⁿ recognition, string copying, and simple accept-all. Covers AQA 7517 Section 3.2 — Theory of Computation.
| State | Read | → New state | Write | Dir | |
|---|---|---|---|---|---|
| No transitions — load an example or add one | |||||
A Turing machine is a theoretical model of computation made up of an infinite tape divided into cells, a read/write head that moves along the tape, a finite set of states, and a transition function that determines the next state, symbol to write and direction to move based on the current state and symbol read. It is used to formally define what it means for a problem to be "computable".
The transition function defines the rules of the machine. For a given current state and the symbol currently under the head, it specifies: the symbol to write to the tape, the direction to move the head (left or right), and the new state to enter. It is often written as a 5-tuple: (current state, read symbol, write symbol, move direction, next state).
A finite state machine (FSM) has a fixed, finite amount of memory — its current state. A Turing machine has an infinite tape it can read from and write to, giving it unbounded memory. This extra memory means a Turing machine can solve problems an FSM cannot, such as recognising languages like 0ⁿ1ⁿ (equal numbers of 0s followed by equal numbers of 1s) which require counting.
No. Turing machines are A Level content only — specifically AQA 7517 Section 3.2 (Theory of Computation). At GCSE you are not required to define or trace Turing machines, though basic ideas about algorithms and computability may appear in A Level theory questions.
A problem is computable if a Turing machine can be constructed that solves it for all valid inputs in a finite number of steps. If no such Turing machine exists — as with the Halting Problem — the problem is described as non-computable (or undecidable).