The Limits of Computation

This lesson is the synthesis of the whole Theory-of-Computation strand. Having built the Turing machine, proved the halting problem undecidable, and classified algorithms by their complexity, we can finally answer the question those lessons were circling: what are the limits of what computers can do? The answer comes in two sharply different kinds. Some problems are impossible — no algorithm to solve them can ever exist, on any machine, given any amount of time. Other problems are possible in principle but infeasible in practice — an algorithm exists, but it would take longer than the lifetime of the universe to finish on realistic inputs. Distinguishing the impossible (undecidable / non-computable) from the merely infeasible (intractable) is the single most important conceptual skill this lesson develops, and it is examined relentlessly. We also look briefly at the physical limits that constrain even the best possible algorithms, and at whether new technologies such as quantum computing change the picture (spoiler: they shift some practical boundaries but move no theoretical ones).

---

Spec Mapping

This lesson draws together the Theory of Computation strand of the AQA A-Level Computer Science specification (7517), spanning both the complexity / classification material (around section 4.4.4) and the model of computation material (around section 4.4.5). You are expected to bring together: intractable problems and the heuristic / approximation responses to them; problems that no algorithm can solve (undecidability, building directly on the halting problem); and the overarching distinction between what is non-computable (impossible), intractable (computable but infeasible) and tractable (efficiently computable). You should be able to explain why each kind of limit holds, illustrate it, and reason about whether faster or future hardware can overcome it. The treatment below is descriptive rather than a verbatim quotation of the specification.

---

The Two Kinds of Limit (and a Third)

There are fundamentally two kinds of barrier to computation, with a third — physical — sitting underneath both. Getting these straight, and never confusing the first two, is the heart of the topic.

Limit	Nature	Can any algorithm solve it?	Example
Theoretical (non-computable / undecidable)	A logical impossibility — no algorithm exists or can ever exist	No — never, on any machine, given any time	The halting problem
Practical (intractable)	Computable, but the resources required grow so fast that large instances are infeasible	Yes — an algorithm exists and is correct; it is just far too slow	Travelling Salesman for 1,000 cities
Physical	Hard limits that physics imposes on any real computing device	n/a — bounds the speed/size of machines, not the solvability of problems	The speed of light; minimum energy per operation

The crucial mental model is a containment hierarchy. All problems split into the non-computable (no algorithm at all) and the computable (some algorithm exists). The computable problems then split into the intractable (no efficient algorithm known) and the tractable (an efficient — polynomial-time — algorithm exists). Physical limits cut across the lot, constraining how fast and small our actual machines can be regardless of which category a problem occupies.

flowchart TB
    All["All problems"]
    All --> NC["Non-computable<br/>(IMPOSSIBLE — no algorithm exists)<br/>e.g. Halting Problem"]
    All --> C["Computable<br/>(an algorithm exists)"]
    C --> INT["Intractable<br/>(INFEASIBLE — no known efficient algorithm)<br/>e.g. TSP, SAT"]
    C --> T["Tractable<br/>(efficient — polynomial — algorithm exists)<br/>e.g. sorting, shortest path"]

---

Theoretical Limits: Uncomputability

The deepest limit is uncomputability: problems for which no algorithm can exist, established rigorously in the previous lesson via the halting problem. These are not problems we have failed to solve yet — they are problems we have proved unsolvable.

• The halting problem — no algorithm can decide, for every program and input, whether the program halts or runs forever.
• The equivalence problem — no algorithm can decide, in general, whether two arbitrary programs compute the same function (produce identical output on every input).
• Rice's theorem — any non-trivial property of the behaviour of a program (does it ever output X? does it always return a positive value? does it access the network?) is undecidable in general.

What makes these limits worth emphasising is that they are absolute. They follow from logic, not from the capabilities of any machine, so:

• No increase in processing speed helps — the halting-problem proof is a logical contradiction that no amount of computation can dissolve.
• No increase in memory helps — the impossibility is independent of resources.
• No future technology helps — by the Church-Turing thesis, neither quantum computers, nor massively parallel supercomputers, nor any device yet imagined exceeds a Turing machine in what it can compute at all. They cannot solve undecidable problems, full stop.

This is the sense in which uncomputability is a mathematical impossibility, categorically different from an engineering challenge. An engineering challenge can be overcome with better technology; a mathematical impossibility cannot be overcome by anything.

---

Practical Limits: Intractability

Among the computable problems, a large and important class is intractable: an algorithm exists and is provably correct, but its running time grows exponentially or factorially, so for realistic input sizes it is hopelessly slow. The problem is solvable in principle and unsolvable in practice — a completely different situation from uncomputability.

The Combinatorial Explosion

Most intractable problems are intractable for the same underlying reason: a combinatorial explosion, in which the number of candidate solutions grows exponentially or factorially with the input size, so that brute-force search becomes impossible almost immediately.

Problem	Input size	Number of possibilities to search
Travelling Salesman (try every tour)	20 cities	$20! \approx 2.4 \times 10^{18}$20!≈2.4×1018
Boolean satisfiability (try every assignment)	50 variables	$2^{50} \approx 1.1 \times 10^{15}$250≈1.1×1015
Subset sum (try every subset)	60 numbers	$2^{60} \approx 1.2 \times 10^{18}$260≈1.2×1018
Protein folding (configurations)	a chain of length $L$L	exponential in $L$L

These numbers are not just "large" — they are larger than any computer could ever enumerate. $2.4 \times 10^{18}$2.4×1018 tours, checked at a billion per second, would still take over 70 years; at 50 cities the factorial reaches $\sim 3 \times 10^{64}$∼3×1064, beyond astronomical. And critically, the explosion outruns hardware: a computer a million times faster lets you add only a handful more cities before you are back at the same wall, because multiplying speed by a constant is no match for factorial growth.

Worked Example: Brute-Force Cryptanalysis

A vivid, real-world illustration is trying to break modern encryption by brute force. The AES-256 cipher uses a 256-bit key, so an exhaustive search must try up to $2^{256} \approx 1.2 \times 10^{77}$2256≈1.2×1077 possible keys. To grasp the scale, imagine an absurdly optimistic attacker:

• suppose every one of the roughly $10^{80}$1080 atoms in the observable universe were a separate computer; and
• suppose each such "computer" could test one trillion ($10^{12}$1012) keys every second.

Even then, the combined machine would test about $10^{92}$1092 keys per second, and exhausting $1.2 \times 10^{77}$1.2×1077 keys would take a fraction of a second — but that is the whole universe-as-computer. Scale it back to any realistic attacker — say a data centre of a billion ($10^9$109) high-end machines each testing a billion keys per second, i.e. $10^{18}$1018 keys/second — and exhausting the key space takes about $1.2 \times 10^{77} / 10^{18} = 1.2 \times 10^{59}$1.2×1077/1018=1.2×1059 seconds, which is roughly $10^{51}$1051 years, against a universe only $\sim 1.4 \times 10^{10}$∼1.4×1010 years old. The brute-force attack is computable — there is a perfectly correct algorithm (try every key) — but it is so far beyond feasible that the encryption is considered secure. This is intractability working for us: the entire field of cryptography is built on problems that are easy to check (decrypt with the right key) but intractable to crack by search.

A Sharp Contrast: Two Similar-Looking Graph Problems

Intractability is not about a problem looking complicated — it is about the growth rate of the best known algorithm. The point is driven home by two graph problems that sound almost identical yet sit on opposite sides of the tractable/intractable line.

Problem	Question	Best known algorithm	Status
Shortest path	What is the cheapest route from node A to node B?	Dijkstra's algorithm, roughly $O(V^2)$O(V2) or $O(E \log V)$O(ElogV)	Tractable (polynomial)
Travelling Salesman	What is the cheapest route visiting every node exactly once and returning to the start?	Brute force $O(n!)$O(n!); best exact methods exponential	Intractable

Both operate on a weighted graph; both ask for a "cheapest route". Yet shortest path is solved in milliseconds for graphs with millions of nodes (your satnav does it constantly), while the Travelling Salesman tour becomes infeasible at a few dozen nodes. The difference lies in the structure of the search. Dijkstra's algorithm can build the shortest path incrementally because an optimal route has the helpful property that any sub-route of it is itself optimal — so the algorithm never needs to reconsider a decision once made, and the work stays polynomial. The Travelling Salesman tour has no such shortcut: choosing the best next city early on can force a disastrous detour later, so there is no known way to avoid, in effect, weighing exponentially many orderings against each other. The lesson for the exam is precise: do not judge tractability by how hard a problem feels — judge it by whether a polynomial-time algorithm is known. Superficially similar problems can differ by an astronomical margin.

Worked Example: Why Intractability and Uncomputability Demand Different Responses

Because the two kinds of limit are so often confused, it is worth working through a scenario that places them side by side. Suppose a software company wants to ship two features: (i) a tool that reports, for any submitted program, whether it will ever enter an infinite loop; and (ii) a tool that finds the cheapest delivery route around a customer's 200 drop-off points.

• Feature (i) is non-computable. Detecting whether an arbitrary program loops forever is the halting problem (or, by Rice's theorem, an undecidable property of program behaviour). No algorithm can do it for all programs, so the correct engineering response is to abandon the goal of a complete tool and instead build an incomplete one — a loop checker that flags many common patterns, warns "may not terminate" when unsure, or restricts itself to a decidable sub-class of programs. No amount of effort or future hardware will ever make the complete version exist.
• Feature (ii) is intractable. Finding the exact optimal 200-point tour is a Travelling Salesman instance: an algorithm exists but would take longer than the age of the universe. The correct response here is different — not to abandon optimality forever, but to approximate it: run a heuristic such as nearest-neighbour followed by 2-opt local improvement, or an approximation algorithm with a proven quality bound. The result is a route that is good enough and computed in seconds.

The two features fail for categorically different reasons and so call for categorically different fixes. Confusing them would be a serious engineering error: chasing a perfect loop detector (impossible) wastes effort that could go into a useful approximate one, while wrongly declaring delivery routing "unsolvable" would abandon a problem that heuristics handle perfectly well in practice. This is exactly why the impossible-versus-infeasible distinction is not academic hair-splitting but a practical decision-making tool.

---

Physical Limits

Even granting a perfect algorithm and unlimited cleverness, the physics of the universe places hard ceilings on any real machine. These are not about which problems are solvable, but about how fast and how small computation can ever be.

Physical limit	What it says	Consequence
Landauer's principle	Erasing one bit of information must dissipate at least $kT \ln 2$kTln2 joules of energy ($k$k = Boltzmann's constant, $T$T = temperature) — about $3 \times 10^{-21}$3×10−21 J at room temperature	Sets a minimum energy cost for irreversible computation; you cannot compute for free
The speed of light	No signal can travel faster than $\approx 3 \times 10^8$≈3×108 m/s	Bounds how quickly distant components can communicate and how fast a signal crosses a chip — a real constraint as clock speeds rise
Bremermann's limit	A self-contained system can process at most $\approx 2 \times 10^{47}$≈2×1047 bits per second per kilogram of mass	Even a computer the mass of the Earth, running for the age of the universe, could perform at most $\sim 10^{93}$∼1093 operations — fewer than $2^{256}$2256
Quantum / atomic scale	As transistors shrink towards individual atoms, quantum effects such as tunnelling make reliable switching impossible	We are approaching the smallest, and so among the fastest, that conventional transistors can be

These bounds reinforce the intractability message from the other direction: there is no physical "loophole" that lets a real machine quietly perform $10^{77}$1077 operations. The universe simply does not contain enough time, energy or matter. Practical infeasibility is therefore doubly assured — by the steep growth of the algorithm and by the finite resources of physics.

---

Can Quantum Computers Break These Limits?

Because quantum computing is so often hyped as limitless, it is worth being precise about exactly what it does and does not change.

It does not overcome any theoretical limit. A quantum computer is, in terms of computability, equivalent to a Turing machine: it can be simulated by an ordinary Turing machine (more slowly) and vice versa. It therefore cannot solve undecidable problems — the halting problem remains unsolvable on a quantum computer just as on a classical one. Uncomputability is untouched.

It can shift some practical (intractability) boundaries — for specific problems with special structure, by providing a faster algorithm: