Undecidability reveals hard limits on what any algorithm can achieve. These are mathematical proofs about what is logically impossible — not engineering constraints.
| Limit Type | Nature | Can it be overcome? | Example |
|---|---|---|---|
| Soft limits | Practical infeasibility (NP-Hard) | Possibly with heuristics/hardware | Travelling Salesman Problem |
| Hard limits | Logical impossibility (undecidable) | Never | Halting Problem |
KEY TAKEAWAY: Soft limits arise from combinatorial explosion and are about time. Hard limits arise from undecidability and are absolute — no amount of computing power can overcome them.
Rice’s Theorem generalises the Halting Problem:
Any non-trivial semantic property of a Turing machine’s language is undecidable.
A property is non-trivial if it is true for some Turing machines and false for others.
Undecidable properties (by Rice’s Theorem):
- Does program $P$ ever output “Hello”?
- Does program $P$ accept any input?
- Do programs $P$ and $Q$ compute the same function?
- Does program $P$ terminate in fewer than 1000 steps on all inputs?
This means: no program analyser can perfectly detect any non-trivial program behaviour for all inputs.
No general algorithm can automatically verify that an arbitrary program meets its specification. Formal verification tools work only on restricted classes of programs or properties.
A perfect virus detector would solve the Halting Problem (detect whether a program ever behaves maliciously on any input). Real antivirus tools use heuristics and signatures — not complete solutions.
Compilers cannot always determine whether dead code will ever execute. They cannot perfectly optimise all programs.
Gödel’s Incompleteness Theorems (connected to Turing’s work): there are mathematical truths that cannot be proved within any consistent formal system. No automated theorem prover can decide all mathematical statements.
| Class | Description |
|---|---|
| Decidable | Always halts correctly |
| P | Decidable in polynomial time |
| NP | Solution verifiable in polynomial time |
| NP-Hard | At least as hard as NP |
| Undecidable | No halting algorithm exists at all |
Undecidable problems are beyond NP-Hard in fundamental difficulty.
EXAM TIP: When asked to contrast hard and soft limits: Soft limits (NP-Hard) — solvable in principle but impractical for large inputs, addressable with heuristics. Hard limits (undecidable) — impossible to solve for all inputs, ever.
STUDY HINT: Connect to real-world consequences: (1) program analysis tools, (2) formal verification, (3) logical systems. These are examined by VCAA.
VCAA FOCUS: Explain the distinction between soft and hard limits. Give real examples of undecidable problems. Explain Rice’s Theorem informally. Link to the Halting Problem as the canonical example.
