Theory of Computation

🎯 Learning Objectives

• Explain abstraction and decomposition, and distinguish representational abstraction, abstraction by reduction, and procedural, functional and data abstraction (AQA 4.2.1, OCR 2.1.5)
• Construct and trace finite state machines with and without output, using state transition diagrams and tables (AQA 4.2.2, WJEC 3.3)
• Recognise and write regular expressions and Backus-Naur Form, and relate each to the class of language it describes (AQA 4.2.2/4.2.3)
• Describe the components of a Turing machine and trace its transition function on a given tape (AQA 4.2.3, WJEC 3.3)
• Explain the significance of the universal Turing machine and the Church-Turing thesis
• Explain what makes a problem computable, and outline the halting problem proof by contradiction (AQA 4.2.3, WJEC 3.3)

📋 Key Definitions and Core Concepts

📌 Key Points

Abstraction and decomposition

Abstraction (AQA 4.2.1, OCR 2.1.5) is the deliberate removal of unnecessary detail. The exam wants you to apply it, not recite it. AQA names four flavours worth quoting:

• Representational abstraction — build a simplified model of a real entity: a road map keeps roads and distances, removes lane widths and colour of buildings; a tube map keeps connections, removes distances entirely.
• Abstraction by reduction — remove detail until the problem is tractable, then categorise what remains as relevant or irrelevant.
• Procedural abstraction — a method hides how behind what: sort(list) hides the algorithm; callers abstract from the implementation.
• Functional abstraction — the result of procedural abstraction viewed purely as a mapping from inputs to output: f(x) = x^2 regardless of how it computes.
• Data abstraction — separate a data structure's logical behaviour from its implementation: a stack is push/pop/LIFO no matter whether it is stored as an array or list.

Decomposition is the companion technique: split a problem into subproblems, solve each (recursively if needed), and combine. The standard 4-marker is 'Explain the benefits of abstraction in solving this problem.' Full-credit structure: (1) state what detail is removed; (2) state why it is irrelevant to the goal; (3) state the consequence — smaller search space, faster to model, easier to reason about, reusable model. Example: modelling a queue at a supermarket — arrivals, service times and number of tills are relevant; customers' items, ages and payment methods are not; the abstracted simulation can be run thousands of times cheaply where the real experiment could not.

The A* link matters too: a heuristic function is abstraction in action — straight-line distance on a map abstracts away road curvature and traffic to give a cheap, admissible estimate. And the link to automation: once a problem is abstracted to a formal model (states, symbols, rules), it can be executed mechanically — which is exactly what a finite state machine or Turing machine is.

Finite state machines

A finite state machine (AQA 4.2.2, WJEC 3.3) has: a finite set of states; an initial state; a transition function moving from state to state on input symbols; optionally a set of accepting states (for an acceptor) or outputs (for a machine with output). Crucially, it has no memory beyond the current state — it cannot count arbitrarily high, which is the fact that limits it to regular languages.

FSM without output (acceptor): drawn as circles with labelled arrows; a double circle is the accepting state. Canonical worked example — accept binary strings containing an even number of 1s:

States: S0 (start, accepting), S1
Transitions:
S0 --0--> S0
S0 --1--> S1
S1 --0--> S1
S1 --1--> S0

State S0 means 'even number of 1s seen so far', S1 means 'odd'. Trace the input 1101: start S0; read 1 → S1 (odd); read 1 → S0 (even again); read 0 → S0; read 1 → S1. End in S1, which is not accepting, so 1101 is rejected (three 1s — odd). Trace 1010: S0→S1→S0→S0→S0, ends in S0, accepted. The idea to internalise: each state summarises everything relevant about the input so far; here a single bit of memory (parity) suffices, so an FSM can do it.

FSM with output (Mealy machine): every transition is labelled input/output, e.g. S0 --1/0--> S1 means 'on input 1, emit 0 and move to S1'. Classic example — a machine that outputs 1 whenever two consecutive identical bits arrive: states track the previous bit; on each input, output 1 if it equals the previous, else 0. Trace input 0110 with previous = none: read 0 → output 0; read 1 → 0 != prev(0), output 0; read 1 → matches prev(1), output 1; read 0 → output 0. Output string 0010. Exam questions also use FSMs for turnstiles, vending machines and locks — the marking points are always: correct number of states, correct initial state, complete transition set (every state has an arrow for every input symbol — a missing transition is a mark lost), and correct accepting/output behaviour.

State transition table is the same machine in tabular form, and exams ask you to convert between the two:

Know also that a transition function written formally as δ(S0, 1) = S1 is just the table in notation. And the significance link: FSMs model state-dependent behaviour — network protocols, lexical analysis in compilers, UI locks — precisely because real systems have finite relevant states.

Regular languages, regular expressions and BNF

A regular language (AQA 4.2.3, WJEC 3.3) is one that a finite state machine can recognise. Regular expressions are the notation for describing them, and the examinable fact is the equivalence: a language is regular if and only if some regular expression (equivalently, some FSM) describes it. OCR also uses regex for pattern matching, e.g. ^[a-z]+[0-9]*$.

Regex syntax to be fluent in:

• a* — zero or more a's; a+ — one or more; a? — zero or one.
• [abc] — any one of a, b, c; [a-z] — any lowercase letter; [^abc] — anything except a, b, c.
• | — alternation: cat|dog; . — any single character; ^/$ — start/end of string.

Worked example: a UK-style vehicle year letter [A-Y] followed by 2–3 digits is [A-Y][0-9][0-9][0-9]?. An even-parity binary string is (0|10*1)* — pairs of 0s and pairs wrapping 0s with 1s keep the count of 1s even; an FSM can recognise it (above), so the language is regular.

What FSMs cannot do: count unboundedly. The language of matched brackets ( ) ( ) ... or a^n b^n needs to remember how many opens are outstanding — arbitrarily many — so no FSM recognises it, and no regular expression describes it. That is where Backus-Naur Form comes in (AQA 4.2.3): BNF is a meta-language of recursive productions describing context-free languages, which strictly contain the regular languages:

   ::= '' |  0 |  1 1 | 1 1 
  ::= '' | (  ) |  
       ::=  |  
     ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The recursion in is what allows arbitrary nesting — the power FSMs lack. Exam question pattern: 'Explain why the following language cannot be described by a regular expression.' Answer structure: identify the unbounded counting requirement (e.g. equal numbers of opens and closes); state that an FSM has finitely many states and no memory beyond the current state, so it cannot count arbitrarily high; conclude the language is not regular and needs a context-free description (BNF) or a pushdown automaton. The hierarchy to quote: regular languages (FSM/regex) are a strict subset of context-free languages (BNF/pushdown), which are a strict subset of all computable (decidable) languages (Turing machine).

Turing machines

A Turing machine (AQA 4.2.3, WJEC 3.3) is the formal model of computation. Components: an infinite tape divided into cells holding symbols (with a blank symbol); a read/write head over one cell; a finite set of states with a start state and halting state(s); and a transition function of the form:

δ(state, symbol) = (new state, symbol to write, move L/R/N)

Unlike an FSM, a Turing machine can read and write the tape, using it as unlimited memory — that is precisely the extra power that makes it a general model of computation. Worked example — increment a binary number, head starting on the rightmost digit, q0 = 'adding 1 with carry', H = halt:

δ(q0, 1) = (q0, 0, L)     // 1+1 = 0, carry propagates left
δ(q0, 0) = (H, 1, N)      // no carry: write 1 and halt
δ(q0, _) = (H, 1, N)      // overflowed left end: append new 1

Trace on tape 1011 (head on last cell): read 1 → write 0, move left (tape now 1010, carry). Read 1 → write 0, move left (1000, carry). Read 0 → write 1, halt (tape 1100). Indeed 1011 + 1 = 1100. Trace on tape 111: 1→0 (L), 1→0 (L), 1→0 (L), blank→1 (H): tape 1000 — the overflow rule appended a digit. Exam marking points: write before moving, carry semantics in the state, and correct halting.

Why Turing machines matter — the two examinable facts:

• Church-Turing thesis: every function that is in any practical sense computable can be computed by a Turing machine. It is a thesis, not a theorem — it cannot be proved, only supported by the fact that every alternative model (lambda calculus, real computers) matches its power. Real computers are Turing-equivalent except for finite memory.
• The universal Turing machine: a single Turing machine that can simulate any other machine M by reading M's transition table (as data) and its input from the tape. This is the theoretical foundation of the stored-program concept — programs are just data that a machine interprets — and of the idea that one general-purpose computer can run any algorithm.

Also know the phrase Turing-complete: a language or system in which every Turing-computable function can be expressed — all mainstream programming languages are. And be ready to compare FSM vs Turing machine in one line: an FSM has a fixed finite number of states and cannot remember unbounded information; a Turing machine's tape gives it unlimited memory, so it can compute anything computable (e.g. a^n b^n, arbitrary arithmetic), where an FSM cannot.

Computability and the halting problem

A problem is computable (decidable) if some algorithm — a Turing machine — solves it correctly for every input in finite time. Problems that are not computable exist, and the exam requires you to know the canonical example and its proof shape (AQA 4.2.3, WJEC 3.3).

The halting problem: given an arbitrary program P and input w, decide whether P eventually halts on w or runs forever. It cannot be solved by any algorithm. The proof is by contradiction:

1. Assume a program H(P, w) exists that always halts and returns true if P halts on w, false otherwise.
2. Construct a new program D(P): if H(P, P) returns true, loop forever; otherwise halt.
3. Now ask what D(D) does. If H says D halts on D, then D(D) loops forever — contradicting H's answer. If H says D does not halt on D, then D(D) halts — again contradicting H.
4. Either way H's answer about D(D) is wrong. So the assumption fails: no such H exists. The halting problem is undecidable.

Practical exam phrasing for a 6-marker: state the problem precisely; state the assumption (a universal decider H exists); describe the construction of D and the self-application D(D); show the contradiction both ways; conclude undecidability. Award points are almost always: correct statement of the problem (1), assumption of H (1), construction of D/D(D) (2), contradiction shown (1), conclusion (1).

Why this matters beyond the proof: the halting problem proves there are limits to computation — no programming language, however powerful, and no future hardware can decide it, because the limitation is mathematical, not technological. Related consequences worth one line each: no tool can perfectly detect all infinite loops or viruses in arbitrary programs (a virus detector that always halts would solve a halting-equivalent problem); some functions are computable but not practically computable because they take exponential time (e.g. brute-force TSP) — distinguish undecidable (no algorithm exists, ever) from intractable (an algorithm exists but is impractical, e.g. O(2^n)).

Exam question pattern: 'State what is meant by a computable problem and give one example of a problem that is not computable.' Answer: a computable problem is one for which there exists an algorithm/Turing machine that produces the correct result in finite time for every input; the halting problem is not computable — no algorithm can decide for every program/input whether it halts, proved by contradiction using a program D that does the opposite of the assumed decider when fed itself.

💡 Worked Example

❓ Practice Questions & Mark Schemes

🎬 Video Resources

• YouTube: A-Level Computer Science Turing machines halting problem finite state machines

📄 Past Papers & Exam Resources

• AQA A-Level Computer Science (7517) past papers and mark schemes
• OCR A-Level Computer Science (H446) — qualifications and assessment materials
• Physics & Maths Tutor — Computer Science revision hub

🔗 Further Reading & Resources

• Physics & Maths Tutor — Computer Science revision (notes and topic questions)
• AQA — find past papers and mark schemes (7517)
• OCR — A-Level Computer Science H446 qualifications page

🧠 Flashcards (Spaced Repetition)

📝 Exam Questions by Topic

🎯 Target Tests (Auto-Graded)

🎓 Smart Lesson (Guided)