Halting problem

The halting problem asks whether an arbitrary program eventually stops when given an input. No algorithm can answer correctly for every program-input pair.

Turing machine: An abstract machine that computes by reading and writing symbols on a tape according to finite rules. The problem is defined over computations that can be represented by these machines.
Computability theory: The study of which problems can be solved by algorithms and which cannot. The halting problem is a foundational example of an unsolvable computational problem.
Rice's theorem: A theorem stating that every nontrivial semantic property of programs is undecidable. It generalizes the halting problem to broad properties of program behavior.
Alan Turing: A British mathematician and computer scientist who formalized computation and proved the halting problem undecidable. His 1936 work supplied the machine model and impossibility proof.
Reduction (complexity theory): A transformation that converts instances of one computational problem into instances of another while preserving answers. Reductions transfer the impossibility of halting decisions to other problems.
Algorithm: A finite, precisely specified procedure for solving a problem or performing a computation. The impossibility concerns every possible algorithm, not merely a particular implementation.
Post correspondence problem: A decision problem asking whether matching sequences can be formed from pairs of strings. Its undecidability can be established by encoding computations related to halting.
On Computable Numbers, with an Application to the Entscheidungsproblem: Alan Turing's 1936 paper introducing abstract computing machines and proving limits on mechanical decision procedures. The paper contains the original argument that no general halting procedure exists.
Diagonal argument: A proof technique that constructs an object differing from every object in a purported complete list. The contradiction uses a program built to disagree with a proposed halting tester on itself.
Gödel numbering: A systematic encoding that assigns numbers to symbols, formulas, or computational descriptions. Encoding programs lets a computation take another program's description as input.

Linked from 32 pages