The Limits of Computation

This lesson brings together the key theoretical concepts to address a fundamental question: What are the limits of what computers can do? Understanding these limits is essential for A-Level Computer Science and for appreciating why some problems remain unsolved despite enormous computational power.

---

Three Types of Limits

Limit	Nature	Example
Theoretical limits	Problems that no algorithm can solve	The Halting Problem
Practical limits	Problems solvable in theory but not in practice due to resource constraints	TSP for 1,000 cities
Physical limits	Constraints imposed by physics on computation speed and miniaturisation	Speed of light, thermodynamics

---

Theoretical Limits: Uncomputability

As established by Turing, some problems are undecidable — no algorithm exists (or can ever exist) to solve them:

• The Halting Problem — cannot determine in general whether a program will halt
• The Equivalence Problem — cannot determine whether two programs are functionally equivalent
• Rice's Theorem — any non-trivial semantic property of programs is undecidable