The halting problem continued

3.1

We have just proven the following

Lemma: The program K halts for an input p iff H(p,p) is false.

Corollary: K halts for the input K iff H(K,K) is false.

By the definition of H, “H(K,K) is false” means that K does not halt

for the input K.

So, replacing in the Corollary

“H(K,K) is false”

by

“K does not halt for the input K”,

we get the following contradiction:

K halts for the input K iff K does not halt for the input K.

We have derived a contradiction from the assumption that the

predicate H(p,i) is decidable, which proves that the assumption was false.

End of proof.

Previous slide

Back to first slide

View graphic version