A-level Computer Science Year 13 · Topic 6
Theory of computation
The theory of computation at A2 level explores the limits and power of computing.
We will study computability and complexity, regular expressions, finite state machines and Mealy machines.
Then we use set theory, Backus Naur form and syntax diagrams, Turing machines, and big O notation to classify problems.
- 7 subtopics
- 156 questions
- Free: 6.1 notes and 10 questions
In this topic
- 6.1Computability and complexityFree below · 23 questions
- 6.2Regular expressions and formal languagesOpen in Full Marks · 20 questions
- 6.3Finite state machines with and without output (Mealy machines)Open in Full Marks · 22 questions
- 6.4Set theory and set notation (subsets, union, intersection, Cartesian product, countability)Open in Full Marks · 19 questions
- 6.5Backus-Naur form and syntax diagramsOpen in Full Marks · 21 questions
- 6.6Turing machines: transition rules and the universal Turing machineOpen in Full Marks · 27 questions
- 6.7Big O notation: time and space complexity, tractable and intractable problemsOpen in Full Marks · 24 questions
6.1 · Free notes
Computability and complexity
Key points
- A Turing machine is a theoretical model of computation with an infinite tape, a read/write head and a set of states and transition rules.
- The halting problem is undecidable: no algorithm can determine, for every program and input, whether it will halt.
- Tractable problems can be solved in polynomial time; intractable problems have no known polynomial-time solution, so heuristics are used.
- Finite state machines have states, inputs and transitions, and can be shown with state transition diagrams or tables.
- Complexity classes describe how resources grow with input size; understanding them guides realistic algorithm choice.
In more detail
- Worked halting proof: suppose H(P, I) always decides whether P halts on I; build D(P) that loops forever if H(P, P) says "halts", and halts otherwise; D(D) then contradicts H, so H cannot exist.
- Worked classes: sorting (O(n log n)) and shortest paths are tractable; brute-force travelling salesman (O(n!)) is intractable.
- Worked factorial growth: 10! = 3 628 800, but 20! ≈ 2.4 × 10¹⁸.
- Worked heuristics: delivery firms plan routes with heuristics, because exact optimal routes would take far too long.
- Worked FSM limit: an FSM cannot check brackets nested to any depth, but a Turing machine can.
Practice
Computability and complexity: 10 questions
Pick an answer to check it, or open the answer for the explanation.
1. What is a Turing machine?
- A physical computer built in 1936
- A theoretical model with an infinite tape, read/write head and states
- A type of compiler
- A network protocol
Show answer
B: A theoretical model with an infinite tape, read/write head and states. It defines what is computable in principle.
2. What does the halting problem show?
- All problems are computable
- Some problems cannot be solved by any algorithm
- Programs always halt
- Recursion is impossible
Show answer
B: Some problems cannot be solved by any algorithm. No general algorithm can decide halting for every program.
3. What is an intractable problem?
- One with no solution at all
- One with no known polynomial-time solution
- One solved in constant time
- One that always halts
Show answer
B: One with no known polynomial-time solution. Heuristic approaches give good-enough answers.
4. What does a finite state machine consist of?
- An infinite tape
- States, inputs and transitions between states
- Only memory addresses
- A hash table
Show answer
B: States, inputs and transitions between states. It can be represented by a diagram or transition table.
5. Why do complexity classes matter in practice?
- They set the programming language
- They show how resource needs grow with input size, guiding algorithm choice
- They determine hardware prices
- They define syntax
Show answer
B: They show how resource needs grow with input size, guiding algorithm choice. An O(2ⁿ) algorithm becomes unusable on large inputs.
6. Which problem is known to be undecidable?
- Sorting a list
- The halting problem
- Binary search
- Matrix addition
Show answer
B: The halting problem. No general algorithm can solve it for all inputs.
7. What is a tractable problem?
- One with no solution
- One solvable in polynomial time
- One requiring exponential time
- One that never halts
Show answer
B: One solvable in polynomial time. Intractable problems grow too fast to solve exactly for large inputs.
8. What is a heuristic?
- An exact algorithm
- A rule of thumb giving a good-enough solution quickly
- A data structure
- A proof technique
Show answer
B: A rule of thumb giving a good-enough solution quickly. Used when exact solutions are impractical.
9. Which two things determine a Turing machine's next action?
- Current state and the symbol under the head
- The previous state and the next symbol
- Tape length and the number of states
- Only the symbol under the head
Show answer
A: Current state and the symbol under the head. Each transition rule maps (current state, symbol read) to a symbol to write, a head move and a new state.
10. An algorithm is O(2^n). The input grows from 10 to 20 items. Roughly how many times more steps are needed?
- 2 times
- About 20 times
- About 1000 times
- About 1 million times
Show answer
C: About 1000 times. 2^20 ÷ 2^10 = 2^10 = 1024, so about 1000 times more steps. Adding items multiplies the work rather than adding to it.
Keep going in Full Marks
Full Marks has 23 questions on Computability and complexity (13 more than here), set out in practice levels. You also get notes and 3D models for all 7 subtopics of Theory of computation, plus games, timed exams and past papers.