Why can't a faster computer solve the halting problem?

Undecidability is independent of speed or memory: the diagonal argument rules out any algorithm whatsoever, no matter how much time it is given. The halting problem is unsolvable in principle, not merely impractical.

Can we ever tell whether a program halts?

Often yes for particular programs, by analysis or by running them. What is impossible is a single algorithm that correctly answers the question for every program and input. Practical termination checkers therefore succeed only on restricted classes or may fail to give an answer.

The Halting Problem and Undecidability

The halting problem, deciding whether a given program halts on a given input, is the canonical example of an algorithmically undecidable problem, and reductions from it prove the undecidability of many others.

Definition

A decision problem is undecidable if no Turing machine decides it correctly on all inputs; the halting problem asks whether an arbitrary machine halts on an arbitrary input, and it is the prototypical undecidable problem from which others are shown undecidable by reduction.

Scope

This topic covers the precise statement of the halting problem, its proof of undecidability by diagonalization, the technique of many-one reduction for transferring undecidability, Rice's theorem on nontrivial properties of programs, and classic undecidable problems such as the Entscheidungsproblem and the word problem for groups.

Core questions

Why is there no algorithm that decides whether programs halt?
How are reductions used to prove one problem undecidable from another?
What does Rice's theorem say about deciding properties of programs?
Which famous mathematical problems turned out to be undecidable?

Key theories

Unsolvability of the halting problem: A diagonal argument shows that assuming a halting decider leads to a contradiction, so no algorithm can decide halting for all programs and inputs.
Reduction and undecidability transfer: If a known undecidable problem reduces to a target problem, the target is also undecidable, making reduction the standard tool for establishing undecidability.
Rice's theorem: Every nontrivial property of the function computed by a program is undecidable, so essentially no interesting behavioral property of programs can be decided algorithmically.

Clinical relevance

Undecidability results establish hard limits on automated reasoning and program analysis: they show that perfect general-purpose tools for verifying termination or program properties cannot exist, and they explain why many problems in logic, algebra, and number theory have no algorithmic solution.

History

Turing and Church showed in 1936 that the Entscheidungsproblem, the question of an algorithm deciding first-order validity, is unsolvable, with the halting problem at the heart of Turing's argument. Rice generalized the phenomenon in 1953, and undecidability was later established for concrete problems such as the word problem for groups by Novikov and Hilbert's tenth problem by Matiyasevich.

Key figures

Alan Turing
Alonzo Church
Henry Gordon Rice
Pyotr Novikov

Seminal works

sipser2013
turing1936
rogers1987

Frequently asked questions

Why can't a faster computer solve the halting problem?: Undecidability is independent of speed or memory: the diagonal argument rules out any algorithm whatsoever, no matter how much time it is given. The halting problem is unsolvable in principle, not merely impractical.
Can we ever tell whether a program halts?: Often yes for particular programs, by analysis or by running them. What is impossible is a single algorithm that correctly answers the question for every program and input. Practical termination checkers therefore succeed only on restricted classes or may fail to give an answer.