What does 4.4 Theory of computation cover?

It covers abstraction and automation as the components of computational thinking, finite state machines with and without output, regular expressions and regular languages, context-free languages described in Backus-Naur Form, Turing machines and the universal Turing machine, and the classification of problems as tractable, intractable, computable or non-computable, including the use of heuristics.

What is the difference between a finite state machine and a Turing machine?

A finite state machine has only a finite number of states and no memory beyond its current state, so it can recognise regular languages but cannot handle unbounded counting or nesting. A Turing machine adds an infinite read/write tape, giving unlimited memory, so it is far more powerful and can compute anything a real computer can. The tape is the key difference.

Why can't a regular expression match balanced brackets?

A regular expression and the finite state machine that recognises it have only finitely many states, so they cannot count without limit or track arbitrary nesting. Matching n opening brackets with n closing brackets needs unbounded memory, which requires a more powerful context-free language defined by a grammar, usually written in Backus-Naur Form.

What is the halting problem?

The halting problem asks whether there is an algorithm that, given any program and input, can decide whether that program will eventually halt or run forever. Alan Turing proved no such general algorithm exists, so the halting problem is non-computable. It shows there are well-defined problems that no computer can solve, which is different from intractable problems that are merely too slow.

What is the difference between an intractable and a non-computable problem?

An intractable problem has a solution in theory but no known algorithm that runs in polynomial time, so it is impractical for large inputs (for example the travelling salesperson problem). A non-computable problem has no algorithmic solution at all, regardless of time (for example the halting problem). Heuristics are used to get good-enough answers to intractable problems quickly.

EnglandComputer Science

AQA A-Level Computer Science 4.4 Theory of computation: abstraction, finite state machines, languages, Turing machines and complexity

A deep-dive AQA A-Level Computer Science guide to 4.4 Theory of computation. Covers abstraction and automation, finite state machines, regular expressions and context-free languages, Turing machines, and the classification of algorithms into tractable, intractable and non-computable problems.

Generated by Claude Opus 4.818 min read4.4Updated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Jump to a section

What 4.4 actually demands
Abstraction and automation
Finite state machines
Regular and context-free languages
Turing machines and complexity
Check your knowledge

What 4.4 actually demands

Theory of computation is the most abstract part of the course. AQA expects you to reason about models of computation and about what can and cannot be computed. The topics build a ladder of increasing power: finite state machines, then context-free languages, then Turing machines, and finally the classification of problems by difficulty.

Abstraction and automation

Abstraction removes unnecessary detail to leave a usable model, in forms such as representational abstraction, generalisation, data abstraction and procedural abstraction. Decomposition breaks a problem into sub-problems, and automation implements a model as algorithms running on hardware. Together these are computational thinking.

Finite state machines

A finite state machine has finite states, a start state and transitions on inputs. Without output it accepts or rejects an input (recognising a regular language); with output (a Mealy machine) it emits output on each transition. You represent it as a state transition diagram or a state transition table.

Regular and context-free languages

A regular expression describes a regular language using concatenation, alternation (|) and repetition (*, +, ?), and is equivalent in power to a finite state machine. Regular languages cannot describe nested structures such as balanced brackets; those need a context-free language defined by a grammar in Backus-Naur Form (BNF), which can be recursive.

Turing machines and complexity

A Turing machine adds an infinite tape and a read/write head, making it more powerful than an FSM; a universal Turing machine can simulate any other, the basis of the stored-program computer. Some problems are non-computable (the halting problem). Problems are tractable (polynomial time) or intractable (no known polynomial algorithm), and heuristics find good-enough answers to intractable problems.

Check your knowledge

Define abstraction. (2 marks)
State the difference between a finite state machine with and without output. (2 marks)
Write a regular expression for one or more digits. (1 mark)
State one kind of language a regular expression cannot describe. (1 mark)
State the key feature that makes a Turing machine more powerful than an FSM. (1 mark)
State what a universal Turing machine can do. (1 mark)
State the difference between a tractable and an intractable problem. (2 marks)
Explain why heuristics are used for intractable problems. (2 marks)

Solutions

Q1: Abstraction is removing unnecessary detail from a problem to focus on the essential features and produce a simplified model.
Q2: Without output (a finite state automaton) the machine only accepts or rejects an input; with output (a Mealy machine) it produces output on each transition.
Q3: (0|1|2|3|4|5|6|7|8|9)+.
Q4: A language with matched nesting, such as balanced brackets; it needs a context-free grammar.
Q5: Its infinite read/write tape provides unlimited memory, which an FSM lacks.
Q6: It can simulate any other Turing machine, given that machine's description and input.
Q7: A tractable problem has a polynomial-time algorithm; an intractable problem has no known polynomial-time algorithm, so it is impractical for large inputs.
Q8: Finding the exact optimal solution to an intractable problem would take impractically long, so a heuristic finds a good-enough (near-optimal) solution quickly.

Sources & how we know this

AQA A-level Computer Science (7517) specification — AQA (2015)