Halting Problem

Alan Turing established the result in his landmark 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," developed independently of Alonzo Church's parallel proof using lambda calculus. Turing himself never used the word "halting" — that term was introduced by Martin Davis around 1952. The proof built on questions raised by David Hilbert's Entscheidungsproblem and resonated with Gödel's 1931 incompleteness theorems.