Abstraction and automation

Abstraction is the removal of unnecessary detail so that the essence of a problem can be reasoned about. AQA distinguishes several kinds:

• Representational abstraction — a model that deliberately throws detail away. The London Underground map is topologically right and geographically wrong, and that is why it works.
• Abstraction by generalisation — grouping things by shared characteristics (a superclass in OOP).
• Procedural abstraction — a subroutine you can call without knowing how it works inside.
• Functional abstraction — you care only about the mapping from input to output.
• Data abstraction — an ADT defined by its operations, not its storage.
• Information hiding — implementation detail is deliberately inaccessible, so it can change without breaking anything.

Automation is putting an abstraction to work: you build a model of a real system and then simulate it — a flight simulator, a climate model, a queueing model of a supermarket. The model is only ever as good as the abstraction it rests on.

Finite state machines

A finite state machine (FSM) is a machine with a finite set of states, one start state, a set of accepting states, and transitions that fire on an input symbol.

• An FSM without output (a finite state automaton) simply accepts or rejects the input string.
• An FSM with output (a Mealy machine) also emits an output symbol on each transition, written input / output.

An FSM can be drawn as a state transition diagram or written as a state transition table.

The limit of an FSM: it has finite memory — the current state is all it remembers. So it cannot count without bound. No FSM can recognise the language aⁿbⁿ (n a's followed by exactly n b's), because it would need unlimited memory to remember how many a's it has seen. That limit is precisely why we need Turing machines.

Your turn — trace the FSM

Regular expressions

A regular expression is a compact way of describing a set of strings — a regular language. The key result: a language is regular if and only if some FSM accepts it. Regular expressions and finite state machines have exactly the same power.

Useful set notation goes with this: ∈ (member of), ∪ (union), ∩ (intersection), ⊆ (subset), ∅ (empty set), and the Cartesian product A × B of all ordered pairs.

Real use: regular expressions drive the lexical analysis stage of every compiler — the tokeniser that recognises identifiers, numbers and keywords is, literally, a finite state machine built from regular expressions.

Your turn — counting strings

The limits of an FSM

Backus-Naur Form

Backus-Naur Form (BNF) is a formal metalanguage for defining the syntax of a language. Compilers use it in the syntax analysis stage.

Read ::= as "is defined as" and | as "or". Symbols in <angle brackets> are non-terminals (defined elsewhere); everything else is a terminal.

The crucial feature is recursion: <number> is defined partly in terms of itself, which lets a finite set of rules describe an infinite set of valid numbers.

Why BNF beats regular expressions: BNF can express nested, balanced structure — matching brackets, nested IF statements — which no regular expression can. BNF describes context-free languages, a strictly larger class than the regular languages. A syntax diagram (railroad diagram) shows the same rules pictorially.

BNF

Turing machines and computability

A Turing machine is the formal model of computation. It has:

• an infinite tape divided into cells, each holding one symbol from a finite alphabet;
• a read/write head positioned over one cell;
• a finite set of states, with a start state and halting states;
• a transition function — given (current state, symbol read) it writes a symbol, moves the head left or right, and changes state.

That is all. Yet the Church-Turing thesis holds that anything that can be computed by any effective procedure can be computed by a Turing machine. A universal Turing machine takes the description of another Turing machine on its tape and simulates it — the theoretical ancestor of the stored-program computer.

Language hierarchy: FSM (regular) ⊂ pushdown automaton (context-free) ⊂ Turing machine (recursively enumerable). Each machine adds memory: none → a stack → an infinite tape.

The halting problem

Some problems are non-computable: no algorithm can exist for them, however clever the programmer and however fast the computer.

The halting problem asks: given any program and any input, decide whether that program will eventually halt or run forever. Turing proved in 1936 that no algorithm can do this for all cases.

The proof, in outline (by contradiction):

• Suppose a program H(P, I) exists that returns True if P halts on input I, and False otherwise.
• Build a new program D(P): it calls H(P, P). If H says "halts", D deliberately loops forever. If H says "loops", D halts.
• Now ask: what does D(D) do? If D(D) halts, then by its own construction it must loop. If D(D) loops, then it must halt.
• Both cases are contradictions. So H cannot exist. ∎

It is not a limit of technology. No future computer, no quantum machine, no amount of memory changes this. It is a limit of computation itself — and it is why no compiler can ever warn you about every infinite loop.

The halting problem

Tractable and intractable problems

Even among computable problems, some are useless in practice. AQA divides them by the complexity of the best known algorithm:

• Tractable — a solution exists in polynomial time: O(1), O(log n), O(n), O(n log n), O(n²), O(n³)… These scale.
• Intractable — the best known algorithm is worse than polynomial: O(2ⁿ), O(n!). A solution exists in theory but not in a usable time for realistic n.

Because intractable problems must still be dealt with, we use a heuristic: a rule of thumb that finds a good enough answer quickly, with no guarantee of optimality. Nearest-neighbour for the travelling salesman, and the estimate function inside A*, are both heuristics.

Your turn — why exponential growth kills

Your turn — brute-force TSP

Tractability

Classify the problems

Tap a problem, then tap the group it belongs to.

Match the term to its meaning

Tap an item on the left, then its partner on the right.

The big ideas to know

That is the whole of AQA 4.4. Press Finish to see your score.