The halting problem
Is the 2-ary predicate “the program p halts for the input i” (the
halting problem) decidable?
Suppose the halting predicate H(p,i) is decidable, i.e. there is a
program HALTS that takes (p,i) as an input and tells us whether
H(p,i) is true or false by, say, typing the words “true” or “false”.
We can assume here that both p and i are binary numbers.
Clearly then we can easily construct another program K which takes
one input p and works as follows: if HALTS prints “true” for the input
(p,p), then K loops forever, and if HALTS prints “false”, then K halts.
In other words, K halts for an input p if and only if the program p
does not halt when it takes itself as an input.