Why can't we just run a program to see if it halts?

Running it tells you it halted only if it actually does; if it is going to run forever, no finite wait reveals that. The halting problem demands a method that always gives the right answer in finite time for every program and input, and Turing proved no such method exists.

Does undecidability make program analysis hopeless?

No, but it explains why perfect analysis is impossible. Tools cope by being conservative, flagging anything they cannot prove safe, by handling restricted classes of programs exactly, or by solving many practical cases while admitting they may fail on adversarial or pathological ones.

Undecidability and the Halting Problem

The halting problem asks whether a given program eventually stops on a given input, and Turing's proof that no algorithm can answer this for all cases is the founding example of an undecidable problem.

Definition

A decision problem is undecidable when no algorithm can correctly answer it for every input; the halting problem, deciding whether an arbitrary program halts on an arbitrary input, is the canonical undecidable problem, proven so by a self-referential diagonal argument.

Scope

This topic covers the diagonalization argument establishing undecidability of the halting problem, the distinction between decidable, recognizable, and co-recognizable problems, Rice's theorem showing that all nontrivial semantic properties of programs are undecidable, and the catalogue of natural undecidable problems across logic, mathematics, and computer science.

Core questions

Why can no single algorithm decide whether every program halts?
What is the difference between a problem being decidable and merely recognizable?
Why are essentially all interesting properties of program behavior undecidable?
How does undecidability spread from the halting problem to other problems?

Key theories

Undecidability of the halting problem: Assuming an algorithm that decides halting leads to a contradiction via a program that halts exactly when it is predicted not to, so no such algorithm can exist.
Rice's theorem: Every nontrivial property of the function computed by a program — anything that holds for some programs and fails for others based on behavior — is undecidable, generalizing the halting result to all semantic properties.

Clinical relevance

Because halting and, by Rice's theorem, all nontrivial behavioral properties of programs are undecidable, no tool can perfectly detect infinite loops, verify arbitrary correctness, or fully analyze every program; static analyzers and verifiers must therefore approximate, accept false alarms, or restrict their scope.

History

Turing established the undecidability of the halting problem and of the decision problem for logic in 1936 using a diagonal argument inspired by Cantor and Gödel. Rice proved his sweeping generalization in 1953, and over the following decades many natural problems, including Hilbert's tenth problem on Diophantine equations, were shown undecidable.

Key figures

Alan Turing
Henry Gordon Rice
Emil Post
Alonzo Church

Seminal works

turing1937
sipser2013

Frequently asked questions

Why can't we just run a program to see if it halts?: Running it tells you it halted only if it actually does; if it is going to run forever, no finite wait reveals that. The halting problem demands a method that always gives the right answer in finite time for every program and input, and Turing proved no such method exists.
Does undecidability make program analysis hopeless?: No, but it explains why perfect analysis is impossible. Tools cope by being conservative, flagging anything they cannot prove safe, by handling restricted classes of programs exactly, or by solving many practical cases while admitting they may fail on adversarial or pathological ones.