Notes · Computer ScienceUK · A-Levels

Theory of computation

This chapter asks the deepest questions in the subject: what does it mean to compute, what can and cannot be computed at all, and how efficiently can the possible be done. It develops computational thinking, the finite state machine and regular languages, Backus-Naur Form for describing syntax, the Turing machine as the definition of computation, the halting problem, and the classification of algorithms by their Big-O complexity - the mathematics that lets you compare algorithms rigorously.

5 sections~18 min reading time3 competenciesLevel Foundation 1 · Standard 1 · Advanced 3

T·0444 / 14

Exam profile

AO1 · Understand abstraction and decomposition, finite state machines, regular expressions and BNF, the Turing machine, computability, and Big-O complexity classesAO2 · Apply FSMs, regular expressions and BNF, and derive the Big-O order of an algorithmAO3 · Reason about what is computable and about the tractability of problems

Operators:explaindescribeapplyderivetraceclassifyevaluate

basic level

AS-Level expects abstraction and decomposition, simple finite state machines and following/writing algorithms.

higher level

The full A-Level adds regular expressions and their equivalence to FSMs, BNF and context-free languages, Turing machines and the halting problem, and the classification of complexity with Big-O including intractability.

Depth

Text

Contents · 5 sections

Theory of computation

Abstraction, decomposition and algorithms#

FoundationAQA 7517 4.4.1DfE GCE Computer Science - computational thinking

Computational thinking is the set of mental tools that turn a real-world problem into something a computer can solve, and its two pillars are abstraction and decomposition. Abstraction is the removal of unnecessary detail so that only what matters to the problem remains: a route-planner abstracts a country to a weighted graph of towns and roads, ignoring the scenery. Representational abstraction decides what to model; procedural abstraction hides how a task is done behind a named subroutine. Abstraction is the single most important idea in computer science - every layer of a computer, from logic gates to applications, is an abstraction built on the one below.

Decomposition (also called problem decomposition or 'divide and conquer') breaks a large problem into smaller sub-problems that can be solved independently and then combined. It makes a problem tractable, allows different people to work on different parts, and produces a solution of well-named subroutines that mirror the structure of the problem. Decomposition and abstraction work together: you decompose a problem into parts and abstract each part behind an interface, so the parts can be reasoned about separately.

An algorithm is a precise, finite, unambiguous sequence of steps that solves a problem or class of problems, and terminates. The A-Level demands fluency in three activities with algorithms: following (tracing) a given algorithm on data to determine its output, writing an algorithm to meet a specification, and correcting an algorithm that contains a fault. Algorithms are expressed in a language-neutral form - pseudocode, structured English, or a flowchart - so that the logic can be reasoned about independently of any programming language.

Automation is the final step: an algorithm, once expressed and abstracted, is turned into a model that a machine executes without human intervention. The power of computing comes from doing this at scale - a payroll algorithm run for a million employees, a search algorithm run billions of times a day. Recognising which parts of a problem can be abstracted, decomposed and automated, and which genuinely require human judgement, is a mark of good computational thinking and is assessed in extended-response questions.

Typical mistakes

Confusing abstraction (removing irrelevant detail) with simply summarising, or failing to state what detail is deliberately ignored.
Writing an 'algorithm' that is ambiguous or has no guaranteed termination - both violate the definition.

Active revision

Explain how you would use abstraction and decomposition to design a program that recommends the fastest bus route across a city, naming two sub-problems and stating one detail you would abstract away.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education) · AQA A-level Computer Science 7517 specification (AQA)

Finite state machines#

StandardAQA 7517 4.4.2DfE GCE Computer Science - finite state machines

A finite state machine (parity of 1s)

Fig. 1An automaton accepting binary strings with an even number of 1s. Even is the start and only accepting state. Reading a 1 switches between Even and Odd; reading a 0 stays in the same state (the self-loops). The string 1011 ends in Even and is accepted; 101 ends in Odd and is rejected.

A finite state machine (FSM) is an abstract model of a system that is always in exactly one of a finite number of states, and moves between them by transitions triggered by inputs. It is defined by a set of states, a designated start state, a set of accepting (final) states, an input alphabet, and a transition function that gives, for each state and input symbol, the next state. FSMs model anything with a fixed, finite memory: traffic lights, vending machines, lift controllers, network protocols, and the lexical analysis stage of a compiler.

An FSM is shown either as a state transition diagram - circles for states, labelled arrows for transitions, a double circle or marked node for an accepting state - or as a state transition table listing the next state for every (state, input) pair. The two are equivalent representations of the same machine; being able to convert between them, and to trace an input string through the machine to decide whether it is accepted, are standard exam tasks. A string is accepted if, starting in the start state and following the transitions for each symbol in turn, the machine ends in an accepting state.

There are two flavours. A finite state machine without output (a finite state automaton) simply accepts or rejects an input - it recognises a language, the set of strings it accepts. A finite state machine with output produces output as it runs: a Mealy machine attaches output to each transition, a Moore machine attaches output to each state. The parity machine opposite is an automaton that accepts binary strings containing an even number of 1s: reading a 1 flips between the Even and Odd states, reading a 0 leaves the state unchanged, and Even is both the start and the only accepting state.

The power of an FSM is also its limitation: because it has only finitely many states, it has only finite memory and cannot count without bound. An FSM can recognise 'strings with an even number of 1s' but cannot recognise 'strings with equal numbers of 0s and 1s' or 'balanced brackets', because these require counting to an arbitrary depth - they need a stack, and so a more powerful model. Exactly the languages an FSM can recognise are the regular languages, which links directly to regular expressions in the next section.

Worked example

Tracing a string through an FSM

Using the parity machine (start Even, accept Even; 1 switches state, 0 keeps it), decide whether the string 1101 is accepted, showing the state after each symbol.

Start
Begin in the start state Even.
Read 1, then 1
First 1: Even to Odd. Second 1: Odd to Even.
Read 0, then 1
0: Even stays Even. Final 1: Even to Odd.

Result: The machine ends in Odd, which is not accepting, so 1101 is rejected. (It contains three 1s - an odd number - as the machine correctly detects.)

Typical mistakes

Forgetting to define a transition for every (state, input) pair, leaving the machine's behaviour undefined on some input.
Judging acceptance by whether a path exists rather than by whether the machine ends in an accepting state after the whole input.

Active revision

Draw the state transition diagram and table for an FSM over the alphabet {a, b} that accepts exactly those strings ending in the substring 'ab'. Then state whether 'aab' and 'aba' are accepted.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Regular expressions, regular languages and BNF#

AdvancedAQA 7517 4.4.3AQA 7517 4.4.4DfE GCE Computer Science - languages

A BNF derivation tree for the number 42

Fig. 2Using the recursive rules number ::= digit | digit number and digit ::= 0..9, the string 42 is derived: a number is a digit (4) followed by a number, which is a digit (2). The leaves read left to right spell 42. Recursion in the rule is what lets a number be any length.

A regular expression is a compact notation for describing a pattern of strings - a language. The core operators are concatenation (symbols in sequence), alternation written with a vertical bar (a

\mid

b means a or b), and the Kleene star (a* means zero or more a's), with a plus for one or more and brackets for grouping. For example

(0\mid 1)0^{*}

describes strings that start with a 0 or a 1 and then have any number of 0s. Regular expressions are used everywhere in practice: validating input, searching text, and defining the tokens a compiler recognises.

There is a fundamental theorem linking the two ideas of this chapter: regular expressions and finite state machines are exactly equivalent in power - every language describable by a regular expression can be recognised by an FSM, and vice versa. The languages they share are called the regular languages. This equivalence is why a compiler's lexical analyser can be specified with regular expressions and implemented as an FSM, and it marks the boundary of what finite memory can do: languages needing unbounded counting (balanced brackets, equal 0s and 1s) are not regular.

Some important languages are beyond regular expressions and need a more expressive notation. Backus-Naur Form (BNF) is a formal way of writing the syntax of a context-free language, using rules that define non-terminal symbols in terms of terminals and other non-terminals. Crucially, BNF rules can be recursive - a rule may refer to itself - which lets them describe nested, arbitrarily-deep structures such as balanced brackets or nested arithmetic expressions that no regular expression or FSM can capture.

A BNF grammar generates strings by repeatedly replacing non-terminals using its rules, and this process can be drawn as a derivation (syntax) tree whose leaves, read left to right, spell the string. The tree opposite derives the two-digit number 42 from the recursive rules

\langle number\rangle ::= \langle digit\rangle \mid \langle digit\rangle\langle number\rangle

and

\langle digit\rangle ::= 0\mid 1\mid \dots \mid 9

. Being able to read a BNF grammar, decide whether a given string is valid, and draw its derivation tree, is core A-Level content - and it explains why programming languages are defined with BNF-style grammars.

Worked example

Matching strings to a regular expression

Which of the strings 'ab', 'aab', 'b', 'aaab' are matched by the regular expression a*b (zero or more a's followed by a single b)?

Interpret a*
a* means zero or more a's, so the string is any run of a's (possibly none) that must then be followed by exactly one b.
Test each
'ab' = one a then b: matches. 'aab' = two a's then b: matches. 'b' = zero a's then b: matches. 'aaab' = three a's then b: matches.

Result: All four match. In fact a*b matches exactly the strings of zero or more a's ending in a single b - the same language a two-state FSM would accept.

Typical mistakes

Reading the Kleene star as 'exactly one' - a* means zero or more, so it also matches the empty string.
Claiming a language such as balanced brackets is regular - it needs unbounded counting, so it is context-free (BNF) but not regular.

Active revision

List three strings matched by the regular expression $1(0\mid 1)^{*}0$ and one that is not. Then, using the grammar $\langle number\rangle ::= \langle digit\rangle \mid \langle digit\rangle\langle number\rangle$ , draw the derivation tree for 507.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Turing machines and computability#

AdvancedAQA 7517 4.4.5DfE GCE Computer Science - computability

A Turing machine tape and head

Fig. 3The infinite tape holds symbols in cells; the read/write head sits over one cell (here reading a 1, highlighted). Each step reads the current symbol, writes a symbol, moves the head one cell left or right, and changes state. The unbounded tape is what gives the machine its full computational power.

A Turing machine is the simplest model powerful enough to capture everything that can be computed. It consists of an infinite tape divided into cells, a read/write head positioned over one cell, and a finite set of states with a transition rule. At each step the machine reads the symbol under the head and, according to its current state, writes a symbol, moves the head one cell left or right, and changes state (shown opposite). Despite this austere design, a Turing machine can compute anything a modern computer can - it is the definition of a general-purpose computer stripped to its essentials.

A Turing machine is more powerful than a finite state machine precisely because its tape gives it unbounded memory: it can move back and forth and store arbitrarily much information, so it can count without limit and recognise the context-free and more complex languages that FSMs cannot. The Church-Turing thesis asserts that any function that can be computed by any effective procedure can be computed by a Turing machine - it is the accepted definition of the word 'computable'. A universal Turing machine is one that takes a description of another Turing machine plus its input and simulates it: the theoretical ancestor of the stored-program computer, where a program is just data.

The most profound result in the subject is that some problems cannot be computed at all, no matter how much time or memory is available. The classic example is the halting problem: there is no algorithm that, given the description of any program and its input, can always correctly decide whether that program will eventually halt or run forever. Alan Turing proved this is undecidable by a contradiction - if such a decider existed, one could build a program that halts exactly when it should loop and loops exactly when it should halt, which is impossible. Non-computable problems set a hard, permanent limit on what computers can ever do.

It is important to separate two different limits. Non-computability (like the halting problem) means no algorithm exists even in principle. Intractability means an algorithm exists but takes so long - typically exponential time - that it is useless for large inputs in practice. Both matter: a problem may be perfectly computable yet intractable, which is why the classification of complexity in the next section is not merely academic but decides which problems we can actually solve.

Worked example

Why the halting problem is undecidable

Outline Turing's argument that no program H can decide, for every program P and input I, whether P halts on I.

Assume a decider exists
Suppose H(P, I) always returns true if P halts on I and false if it loops forever - a perfect halting decider.
Build a contrary program
Construct a program X that, given a program P, runs H(P, P) and then does the opposite: if H says 'halts', X loops forever; if H says 'loops', X halts.
Feed X to itself
Ask what X does on input X. If X halts, then H(X, X) said 'halts', so by construction X loops - contradiction. If X loops, H said 'loops', so X halts - also a contradiction.

Result: Both cases are contradictory, so the assumed decider H cannot exist. The halting problem is undecidable - a permanent limit on what any computer can do.

Typical mistakes

Confusing non-computability (no algorithm can exist) with intractability (an algorithm exists but is too slow) - they are different limits.
Thinking the halting problem is only unsolved rather than provably impossible for a general decider.

Active revision

Explain why a Turing machine can recognise the language of balanced brackets while a finite state machine cannot, then state in your own words what the halting problem shows about the limits of computation.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education)

Big-O and the classification of complexity#

AdvancedAQA 7517 4.4.6DfE GCE Computer Science - complexity

How complexity classes grow

Fig. 4Operations against input size

n

O(1)

and

O(\log n)

stay almost flat,

O(n)

rises steadily, and

O(n\log n)

and especially

O(n^2)

climb steeply. Beyond the top of the axis

O(n^2)

(and, off the chart,

O(2^n)

) rapidly become impractical - the visual case for choosing a lower-order algorithm.

Big-O notation measures how an algorithm's running time (or memory) grows as the input size

n

grows, keeping only the dominant term and ignoring constant factors. It captures the shape of the growth, which is what determines whether an algorithm scales. The standard classes, from best to worst, are constant

O(1)

, logarithmic

O(\log n)

, linear

O(n)

, linearithmic

O(n\log n)

, polynomial (e.g. quadratic

O(n^{2})

or cubic

O(n^{3})

) and exponential

O(2^{n})

. The plot opposite shows how sharply they diverge: as

n

grows the higher classes explode while the lower ones stay almost flat.

You find an algorithm's complexity by counting how its basic operations depend on

n

. A single indexed array access is

O(1)

- independent of size. Halving the problem each step, as binary search does, gives

O(\log n)

. One loop over the input is

O(n)

; the classic efficient sorts are

O(n\log n)

. Nested loops over the input give polynomial time - two nested loops are

O(n^{2})

, as in bubble sort - and generating every subset or trying every combination gives exponential

O(2^{n})

. When several parts run in sequence, the largest (dominant) term wins, so

O(n^{2} + n)

is simply

O(n^{2})

The practical dividing line is between tractable and intractable problems. A problem is tractable if an algorithm solves it in polynomial time or better (

O(n^{k})

for some constant

k

) - these scale to large inputs. A problem for which the only known algorithms are exponential (or worse) is intractable: the table opposite shows why. At

n = 100

, an

O(n^{2})

algorithm does ten thousand operations, but an

O(2^{n})

algorithm does about

10^{30}

- more than the age of the universe in nanoseconds. Intractable problems (like the travelling salesman in its exact form) are computable but hopeless to solve exactly for large inputs, so heuristics that find good-enough answers are used instead.

Two subtleties are examined. First, Big-O is a worst-case bound - it describes the guarantee, though best- and average-case behaviour can differ (linear search is

O(n)

worst case but

O(1)

if the target is first). Second, constant factors and lower-order terms are deliberately dropped, so Big-O compares scalability, not raw speed on small inputs - an

O(n^{2})

algorithm can beat an

O(n\log n)

one for tiny

n

, but for large

n

the asymptotic class always wins. Deriving the Big-O of a given piece of code by counting its loops is a standard, high-value exam skill.

O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)

The complexity hierarchy

Ordered from most to least scalable; each class grows strictly faster than the one before as $n$ increases.

Operations required at different input sizes

Fig. 5The number of basic operations each complexity class needs at n = 10 and n = 100. The polynomial classes grow manageably, but O(2^n) explodes from about a thousand to a number with thirty digits - the essence of intractability.

Worked example

Deriving the complexity of nested loops

State the Big-O time complexity of this fragment and justify it: FOR i = 1 TO n; FOR j = 1 TO n; print(i, j); NEXT j; NEXT i.

Count the inner loop
For each fixed i, the inner loop runs n times, doing $O(1)$ work per iteration - so the inner loop is $O(n)$ .
Count the outer loop
The outer loop runs n times, and each of its iterations performs the $O(n)$ inner loop, giving $n \times n = n^2$ print operations.
Report the dominant term
The total work is proportional to $n^2$ ; constants and lower-order terms are dropped.

Result: The fragment is $O(n^2)$ - quadratic. Doubling n quadruples the work, which is why nested loops over the whole input do not scale to large n.

Typical mistakes

Keeping constant factors or lower-order terms - $O(3n^{2} + 5n + 2)$ is simply $O(n^{2})$ ; only the dominant term, without its coefficient, is reported.
Confusing $O(n\log n)$ with $O(n^{2})$ , or assuming more nested loops always means higher order regardless of what they iterate over.

Active revision

State the Big-O time complexity of: (a) accessing array[5]; (b) a single loop summing n items; (c) two nested loops each running n times; (d) binary search. Then explain, using $n = 50$ , why an $O(2^{n})$ algorithm is intractable.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

References & sources

Sources

Department for Education

GCE AS and A level subject content for computer science

AQA

AQA A-level Computer Science 7517 specification

Theory of computation

5 sections~18 min reading time3 competenciesLevel Foundation 1 · Standard 1 · Advanced 3

Theory of computation

Key points

Key points

Tracing a string through an FSM

Key points

Matching strings to a regular expression

Key points

Why the halting problem is undecidable

Key points

Deriving the complexity of nested loops

Sources

Theory of computation

Key points

Key points

Tracing a string through an FSM

Key points

Matching strings to a regular expression

Key points

Why the halting problem is undecidable

Key points

Deriving the complexity of nested loops

Sources