1. 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
    haltsif T does not halts on input T*
    fails to haltsif T halts on input T*
  2. What happens when S is given S* as input?

    haltsif T does not halts on input S*
    fails to haltsif T halts on input S*
    This table embodies a contradiction.
We must conclude that P does not exist and that the Halting Problem is unsolvable.

CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000