← Computer Science syllabus

EnglandComputer Science

4.4 Theory of computation

5 dot points across 5 inquiry questions. Click any dot point for a focused answer with worked past exam questions where available.

What are abstraction and automation, and how do we solve problems computationally?

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.
8 min answer →

How are problems and algorithms classified by how hard they are to solve?

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.
8 min answer →

What is a finite state machine and how is it represented?

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.
8 min answer →

What are regular expressions, and how do regular and context-free languages differ?

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.
9 min answer →

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.
8 min answer →