HookThe problem no computer will ever solve
In 1936 a 24-year-old named Alan Turing answered a question the mathematician David Hilbert had left open: is there a mechanical procedure that can decide whether any given mathematical statement is provable? To attack it Turing invented an imaginary machine — an infinite paper tape, a read/write head, and a finite table of rules — and asked what such a device could and could not do. His answer reshaped the century. He described the halting problem: feed a machine any program together with its input and ask whether that program will eventually stop or loop forever. Turing proved that no single algorithm can answer that question for every possible program. Not slowly. Never.
That proof draws the outer wall of this entire topic. Everything else in Theory of Computation happens inside it and is really one skill practised at different scales: taming complexity. You abstract a messy real situation down to what a machine can process, decompose it into sub-problems, describe the patterns a machine can recognise using finite state machines, regular expressions and Backus-Naur Form, and measure whether your algorithm is quick enough to be worth running using Big-O. Of every section on the A-level, this one punishes vague vocabulary hardest: calling an algorithm slow without a complexity class, or muddling abstraction with decomposition, is exactly where marks drain away.
ModelThe many faces of abstraction
Abstraction is the removal of unnecessary detail so that only what matters to the problem remains. Harry Beck's 1931 London Underground map is the classic case: he threw away true distances, curves and surface geography and kept only which stations connect to which, because that is all a passenger navigating the network actually needs. The A-level then splits abstraction into named varieties, and the exam expects you to tell them apart.
Representational abstraction, also framed as problem abstraction or reduction, means stripping detail away until what is left is a problem you already know how to solve. Information hiding is concealing the internal details of a component so the rest of the system neither sees nor depends on them — you use a module through its interface only. Procedural abstraction names a sequence of steps as a procedure and lets you call it without knowing its internals; functional abstraction pushes that further, so you care only about the mapping from inputs to a returned result and never about how it is computed. Data abstraction separates the logical behaviour of a structure — a stack offers push and pop — from its physical implementation as an array or a linked list. Each variety buys the same thing: the freedom to change what is hidden without breaking what relies on it.
ModelBreaking problems down, building solutions up
A computational approach to problem-solving starts by pinning down the inputs, the required outputs and the process that links them. Decomposition then breaks a large problem into smaller sub-problems that can each be understood and solved on their own — a payroll system becomes read-hours, calculate-gross, apply-tax and produce-payslip. Composition is the reverse move: reassembling those separately solved procedures into a working whole, which only stays manageable if each part was given a clear interface. Automation is building a model of a real-world process and letting a computer execute it — a traffic-flow simulation or a climate model is automation, not merely software running.
An algorithm is a finite sequence of unambiguous steps that is guaranteed to terminate, usually written as pseudocode or a flowchart. Following one by hand with a trace table — a column per variable and a row per step — is a guaranteed exam task, and crucially it is a different skill from understanding why the algorithm works: you can trace a method correctly without grasping the maths behind it. Practise tracing until it is mechanical, because the marks are for the intermediate values, not just the final output.
Trace Euclid's algorithm for the greatest common divisor of 48 and 18. The loop is: WHILE b is not 0, temp ← b, b ← a MOD b, a ← temp, ENDWHILE, OUTPUT a.
Start with a = 48, b = 18. Pass 1: temp = 18, b = 48 MOD 18 = 12, a = 18. Pass 2: temp = 12, b = 18 MOD 12 = 6, a = 12. Pass 3: temp = 6, b = 12 MOD 6 = 0, a = 6. Now b = 0, the loop condition fails and the algorithm outputs a = 6. Laid out as a trace table those three rows expose the answer, 6, one state at a time. Notice you reached the correct result without ever needing to prove why Euclid's method finds the GCD — the trace verifies the behaviour, not the theory, which is exactly the split the exam tests.
ModelFinite state machines: memory of exactly one thing
A finite state machine (FSM) is the simplest useful model of computation: a finite set of states, one marked as the start, transitions triggered by input symbols, and — for an acceptor — a set of accepting states. Its defining limitation is that it remembers nothing except which state it is currently in. An FSM without output is an acceptor: after reading the whole input it either sits in an accepting state (the string belongs to the language) or it does not. An FSM with output, a Mealy machine, emits an output symbol on each transition — the arc is labelled input / output — which is how an FSM models something active like a serial adder or a lift controller. Both are drawn as state transition diagrams and can be written as a state transition table listing, for every state and every input symbol, the next state.
Build an acceptor for binary strings containing an even number of 0s. Two states are enough: S0 (an even count of 0s so far, and the accepting state) and S1 (an odd count). Reading a 1 changes the count of 0s not at all, so 1 loops on the current state; reading a 0 flips between S0 and S1. Start in S0.
Trace the input 1001: start S0, read 1 stay in S0, read 0 move to S1, read 0 move back to S0, read 1 stay in S0. The machine ends in S0, an accepting state, so 1001 (which contains two 0s) is accepted. Feed it 100 instead and it ends in S1 and is rejected — one 0 short of even. The machine never counts the 0s; it only ever knows their parity, which is precisely why an FSM can decide even-ness but could never check that a string of brackets is balanced.
ModelLanguages, sets and regular expressions
Formally a language is just a set of strings, which is why the maths behind this section is set theory. You are expected to read and use set notation: membership (∈), union (∪), intersection (∩), subset (⊆), the empty set (∅), cardinality (the size of a finite set) and the Cartesian product. Sets can be finite or countably infinite — the set of all binary strings is infinite yet can be listed in a definite order, a fact that matters later for deciding what is and is not computable.
A regular expression is a compact pattern describing such a set of strings. The operators are concatenation, | for alternation (or), * for zero-or-more, + for one-or-more, ? for zero-or-one, and parentheses for grouping. A regular language is any language that a regular expression can describe — and the deep result of the section is that regular expressions and finite state machines have exactly the same power: every regular expression can be converted into an FSM that accepts the same strings, and every FSM into a regular expression. They are two notations for one idea.
The regular expression 1(0|1)* describes every binary string that starts with a 1. Read it left to right: a literal 1, followed by zero or more symbols, each of which is a 0 or a 1. So it matches 1, 101 and 1110, but rejects 0 and 011 because they do not begin with 1. Written as a set in comprehension form it is the set of strings s such that s begins with 1. Because this is a regular language, you could equally draw a small FSM whose start state accepts only after a leading 1 and then loops on any further 0 or 1 — the expression and the machine recognise exactly the same set.
ModelBNF: grammar beyond the reach of regular expressions
Backus-Naur Form (BNF) is a notation for defining the syntax of a language using rules. Each rule defines a non-terminal (a name written in angle brackets) in terms of terminals (literal symbols that appear in the language) and other non-terminals, using ::= to mean is defined as and | to separate alternatives. Its real advantage over a regular expression is recursion: a rule may refer to itself, which lets BNF describe nested, self-similar structures — balanced brackets, arithmetic expressions, the full grammar of a programming language — that no regular expression can capture. That gap is a favourite exam point: some languages can be defined in BNF but are not regular, because a finite state machine has no way to count arbitrary depth of nesting. Syntax diagrams (railroad diagrams) are the graphical equivalent, where any complete path traced through the diagram spells out a valid string.
Define an unsigned integer. A digit is any single numeral, and an unsigned integer is either one digit or a digit followed by another unsigned integer — a recursive rule:
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <uint> ::= <digit> | <digit> <uint>
Derive the string 42 by repeatedly replacing a non-terminal with one of its alternatives: <uint> becomes <digit><uint>, then 4<uint>, then 4<digit>, then 42. The self-reference inside <uint> is what lets a fixed-size rule generate integers of any length — the very trick no regular expression can imitate for genuinely nested structures, and the reason BNF is used to specify real programming languages.
DataComparing algorithms with Big-O
To compare algorithms fairly you measure how their resource use grows with the size of the input, n, rather than timing them once on one machine. Time complexity counts operations; space complexity counts memory; both are usually quoted for the worst case. Big-O notation captures the dominant term of that growth and discards constants and lower-order terms, because as n grows the highest-order term swamps everything else. The maths you need is the shape of the common functions — constant, logarithmic, linear, linearithmic, polynomial and exponential — and how each behaves as n rises. The order of complexity ranks them from best to worst: O(1), then O(log n), O(n), O(n log n), O(n²), O(2ⁿ) and O(n!). Anything O(n²) or worse scales badly, and exponential or factorial orders become useless beyond very small inputs.
Bubble sort compares every adjacent pair on each of its passes, so on 5 items it does at most 4 + 3 + 2 + 1 = 10 comparisons, and in general n(n−1)/2. Dropping the constant and the lower-order term leaves O(n²): double the list and the work roughly quadruples. Binary search instead halves the search space at every step, so a sorted list of 1,000,000 items is found in at most about 20 comparisons, because 2²⁰ is just over a million — that is O(log n). The contrast is the whole point of the section: on a million items, an O(n²) algorithm faces roughly a trillion operations while an O(log n) one needs about twenty, and no faster processor closes a gap that large. That is why choosing the algorithm beats buying the hardware.
CaseThe edge of the possible
Some problems cannot be solved quickly, and some cannot be solved at all — this is the classification of algorithmic problems. A tractable problem has an algorithm that runs in polynomial time, O(n), O(n²) or O(n³), and stays practical as n grows. An intractable problem has only solutions of exponential or worse order, so it is theoretically solvable but hopeless for real input sizes; brute-forcing the travelling salesman's shortest route is the standard example. Beyond both lies the non-computable: problems for which no algorithm exists at any speed.
The halting problem is the headline non-computable problem. Suppose an algorithm H could take any program and any input and correctly report whether that program halts. Turing showed you could then build a program that deliberately halts exactly when H predicts it will loop, and loops exactly when H predicts it will halt — a direct contradiction — so H cannot exist. The model underneath all of this is the Turing machine: a finite state machine coupled to an infinite tape it can read and write. A universal Turing machine can simulate any other, which is the theoretical ancestor of the stored-program computer, and the Church-Turing thesis holds that anything computable at all is computable by a Turing machine. Keep non-computable and intractable strictly apart: one means no algorithm exists, the other means every algorithm is simply too slow.
VocabularyKey terms the mark scheme pays for
TrapsMisconceptions that cost marks
ExamWhat examiners want
Theory of computation is assessed mainly on the written Paper 2 (7517/2), and it rewards AO1 precision above almost anything else on the course. Definitions must be exact and not interchangeable: abstraction removes detail, decomposition splits a problem into sub-problems, and information hiding conceals internals — a mark scheme will not accept one term used for another. For finite state machines, always state the start state and the accepting state(s) and label every transition with its input symbol (and, for a Mealy machine, its output); an unlabelled arc scores nothing, and a missing accepting state can lose the whole answer. For Big-O questions, give the order class and justify it from the code's structure — nested loops over n give O(n squared), repeated halving gives O(log n) — because that justification is where the AO2 application marks sit.
On the harder ideas, structure earns the credit. A halting-problem answer should follow the proof-by-contradiction shape: assume the deciding algorithm exists, construct the self-contradicting program from it, and conclude that the decider cannot exist. Keep non-computable and intractable strictly separate, since examiners set questions specifically to catch students who blur them. In BNF questions, show every substitution step in a derivation rather than jumping straight to the final string, and remember the standard discriminator to quote in extended answers: if a language requires unbounded counting or nesting it is not regular, so it needs BNF rather than a regular expression or a plain finite state machine.