Textbook of AI

The halting problem asks: given a description of an arbitrary Turing machine M and an input w, does M halt when run on w? Alan Turing proved in 1936 that this problem is undecidable, no algorithm can solve it for all inputs.

The proof is a classical diagonal argument. Suppose, for contradiction, that there were a Turing machine H that takes (M, w) and halts with output 1 if M halts on w, 0 otherwise. Construct a new machine D that, given input M, runs H on (M, M); if H outputs 1, D loops forever; if H outputs 0, D halts. Now ask: does D halt on input D? If yes, then by construction D loops; if no, then D halts. Contradiction. Therefore H cannot exist.

The halting problem is the prototype of an undecidable problem. By Rice's theorem (1953), any non-trivial semantic property of programs , does this program ever output 7? does it allocate unbounded memory? is it equivalent to that other program?, is undecidable. The result places hard limits on automated program analysis, formal verification, type-checking and theorem proving; practical systems work around it by trading completeness for soundness, or by restricting attention to decidable fragments.

For AI safety the halting problem implies that no fully general algorithm can certify that an arbitrary AI system will not enter an unintended loop, exceed a resource budget, or violate a specification. Bounded approximations, using time and memory limits, restricted languages, or sound static analyses, remain the only practical option.