What is a Turing machine and why does it matter for the theory of computation?
Understand the Turing machine model, its components, the idea of a universal Turing machine, and the link to the limits of computation and the halting problem.
A focused answer to AQA A-Level Computer Science 4.4.5, covering the Turing machine model and its components, the transition rules, the universal Turing machine, and its link to computability and the halting problem.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this dot point is asking
AQA wants you to describe the Turing machine model and its components, write or read transition rules, explain the universal Turing machine, and connect Turing machines to what is and is not computable, including the halting problem.
The Turing machine model
A transition rule has the form: in the current state, reading a given symbol, the machine writes a symbol, moves the head left or right, and changes to a new state. The machine halts when no rule applies or it reaches a halting state.
(state, symbol read) -> (symbol to write, move L/R, next state)
The tape is the crucial element. Unlike registers or a fixed memory, it is unbounded, so the machine never runs out of working space. By writing and rereading symbols on the tape, the machine can remember arbitrarily much, which is what lets it perform any computation a real computer can. The model is deliberately minimal so that arguments about what can and cannot be computed are clean and general.
Why it is powerful
This places the Turing machine at the top of a hierarchy studied in this module: a finite state machine recognises regular languages, a pushdown machine handles context-free languages, and a Turing machine handles everything computable. Each step up adds memory power, with the Turing machine's unbounded read/write tape being the most powerful. The Church-Turing thesis is the claim that this is as far as it goes: no realisable model of computation can do more than a Turing machine.
The universal Turing machine and computability
The halting problem is the key example of a limit on computation, and it matters because it is not a question of speed but of possibility: no algorithm can ever decide it for all inputs. This distinguishes non-computable problems (no algorithm exists at all) from merely intractable ones (an algorithm exists but is too slow), a distinction examined alongside this dot point in the classification of algorithms.
Exam-style practice questions
Practice questions written in the style of AQA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
AQA 20194 marksDescribe the components of a Turing machine and explain why a Turing machine is considered more powerful than a finite state machine.Show worked answer →
A Turing machine consists of an infinitely long tape divided into cells (each holding a symbol), a read/write head that can read and write the symbol under it and move one cell left or right, a finite set of states including a start state, and a set of transition rules that, given the current state and the symbol read, specify the symbol to write, the direction to move and the next state.
A Turing machine is more powerful than a finite state machine because the tape provides unlimited memory that can be both read and written, so it can count without bound and handle nested or matched structures (such as balanced brackets) that a finite state machine, having only finitely many states, cannot. This lets a Turing machine recognise languages beyond the regular and context-free, in fact anything computable.
Markers reward listing the tape, head, states and transition rules, and the unlimited read/write memory of the tape as the reason for the extra power over an FSM.
AQA 20214 marksExplain what a universal Turing machine is and how it relates to the stored program concept used in modern computers.Show worked answer →
A universal Turing machine (UTM) is a single Turing machine that can simulate any other Turing machine, given a description of that machine and its input written on the tape. In other words, one fixed machine can carry out the behaviour of any specific machine when that machine is supplied to it as data.
This relates directly to the stored program concept: in a modern computer, programs are stored in memory as data and the processor reads and executes them, so the same hardware can run any program. The UTM is the theoretical foundation of this idea, showing that a single general-purpose machine can perform any computation by being given the right program as input.
Markers reward defining the UTM as a machine that simulates any other given its description, and linking it to programs stored as data on general-purpose hardware (the stored program concept).
Related dot points
- Understand finite state machines with and without output, state transition diagrams and tables, and the use of an FSM to recognise inputs or model behaviour.
A focused answer to AQA A-Level Computer Science 4.4.2, covering finite state machines with and without output, state transition diagrams and tables, and using an FSM to recognise inputs or model behaviour.
- Understand regular expressions and regular languages, the link between regular expressions and finite state machines, the limits of regular languages, and context-free languages described by a BNF grammar.
A focused answer to AQA A-Level Computer Science 4.4.3 and 4.4.4, covering regular expressions and regular languages, their link to finite state machines, the limits of regular languages, and context-free languages described using BNF.
- Understand tractable and intractable problems, the classes P and NP, the idea of computable and non-computable problems, and the use of heuristics for intractable problems.
A focused answer to AQA A-Level Computer Science 4.4.6 and 4.4.7, covering tractable and intractable problems, the classes P and NP, computable and non-computable problems, and the use of heuristics to tackle intractable problems.
- Understand abstraction, the different forms of abstraction, decomposition, automation, and the components of computational thinking used to solve problems.
A focused answer to AQA A-Level Computer Science 4.4.1, covering abstraction and its forms, decomposition, automation, and the components of computational thinking used to solve problems with computers.
- Understand the stored program concept, the Von Neumann architecture, the Harvard architecture, and the differences between them.
A focused answer to AQA A-Level Computer Science 4.7.2, covering the stored program concept, the Von Neumann architecture, the Harvard architecture, and the differences between them.
Sources & how we know this
- AQA A-level Computer Science (7517) specification — AQA (2015)