Unsolvability of The Halting Problem

Assume that P is a Turing machine that takes as input the encoding T* of a Turing machine T and an input t for that Turing machine and that solves the halting Problem. In particular, P always halts and its outputs are:

 0 if T does not halt on input t 1 if T halts on input t.

Use P to build a Turing machine Q that takes as input the encoding T* of a Turing machine T and an input t for that Turing machine and that halts exactly when P outputs a 0. the result of executing Q is:

 halts if T does not halt on input t fails to halt if T halts on input t.

Finally, use Q to build a Turing machine S that takes as input the encoding T* of a Turing machine T, makes a copy of T* and feeds (T*,T*) to Q. The result of running S is

 halts if T does not halt on input T* fails to halts if T halts on input T*

What happens when S is given S* as input?

 halts if S does not halt on input S* fails to halts if S halts on input S*

We must conclude that P does not exist and that the Halting Problem is unsolvable.

The whole proof is a variant on the old Liar's Paradox:

I am (always) a liar.

This statement is false.

Is this statement true or false?

CS1104 Main Page
Last Updated 01/05/2000