We usually meet a hard problem and assume that with enough cleverness, time and memory we could crack it. Sorting a billion names, factorising a huge number, playing perfect chess — these are slow, maybe astronomically slow, but an algorithm for each one clearly exists. So here is a genuinely startling claim, and the heart of this page:

Some problems cannot be solved by any algorithm at all. Not "not yet", not "only with a faster computer", not "only in a trillion years" — never, on any machine, with unlimited time and memory. We call such problems non-computable (or undecidable). Their existence is not a practical grumble about slow hardware; it is a hard mathematical limit on what computation can ever do.

The most famous example was found by Alan Turing in 1936, before the first electronic computers had even been built. It is called the halting problem, and by the end of this page you will be able to prove — properly, not just be told — that no program can solve it.

Halting versus looping forever

Every program you run does one of two things. Either it eventually halts — reaches the end, stops, gives an answer — or it loops forever, grinding away and never stopping. Compare these two tiny snippets:

For these two it is obvious which is which. But in general, deciding whether a program halts can be fiendishly subtle. Consider a program that starts at some whole number and repeats: "if it's even, halve it; if it's odd, triple it and add one", stopping only when it reaches 1. Nobody on Earth knows whether that program halts for every starting number — it's a famous unsolved puzzle (the Collatz conjecture). The halting problem asks for something much more ambitious than any one puzzle: a single, general method that works for all programs at once.

The dream machine: halts(P, input)

Imagine we had a perfect analyser — call it halts. You feed it any program P together with the input you plan to give P, and without ever running P it instantly and correctly reports one of two answers:

Such a tool would be worth a fortune: it would spot every infinite loop before shipping, prove that any piece of software eventually finishes, and settle countless open problems in an afternoon. Turing's argument shows, devastatingly, that halts cannot exist. We prove it by contradiction: we assume it exists, then build something that breaks it.

The trap: a program that does the opposite

Suppose halts really exists. Then we are allowed to use it inside other programs. So let's write a mischievous little program — call it troublemaker. It takes a program P as its input, asks halts what P would do when fed a copy of itself, and then deliberately does the opposite:

Read it slowly. troublemaker is perfectly legal to write — it's just an if with two branches. Its whole personality is contrariness: whatever halts predicts about a program run on itself, troublemaker guarantees the reverse.

Now spring the trap. Run troublemaker on itself: feed it troublemaker as the input P. Watch the diagram step through the paradox.

Why it's a paradox

Consider the two — and only two — possibilities for what troublemaker(troublemaker) does:

• Suppose it halts. Then halts(troublemaker, troublemaker) must have returned true. But look at the code: when the answer is true, troublemaker takes the "loop forever" branch. So it does not halt. Contradiction.
• Suppose it loops forever. Then halts(troublemaker, troublemaker) must have returned false. But when the answer is false, troublemaker takes the "stop" branch — so it does halt. Contradiction again.

Every possibility contradicts itself. The program can neither halt nor run forever, which is absurd — real programs always do exactly one of those. The only thing we assumed along the way was that halts existed. So that assumption must be false:

This is the same self-referential twist as the old sentence "this statement is false" — the machine is asked a question about itself and is then built to defy its own answer. Turing turned that ancient liar's paradox into a precise theorem about computers.

So what does this mean for real computing?

The halting problem sounds abstract, but its shadow falls across everyday software engineering, because many practical questions secretly contain it:

• Perfect bug-finding is impossible. No tool can look at any program and always correctly say "this will never crash" or "this loop always terminates". Real analysers therefore either give up on some inputs ("can't tell"), or play safe and sometimes cry wolf.
• Perfect virus detection is impossible. Deciding whether an arbitrary program will ever do something malicious is undecidable too, which is why antivirus tools rely on heuristics and signatures rather than a proof.
• Compilers can't optimise everything. Many "will this ever happen?" questions a compiler would love to answer turn out to be undecidable, so it must be conservative.

The lesson is not despair — engineers build superb approximate tools. The lesson is humility: there is a hard ceiling on what computation can promise. A whole family of other problems can be shown undecidable by reducing them to the halting problem — "if I could solve this, I could solve halting; but I can't solve halting, so I can't solve this either."