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*

    This table embodies a contradiction.

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
© L.Heath, 2000