We must conclude that P does not exist and that the Halting Problem is unsolvable.
- 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 halts on input T*
|fails to halts||if T halts on input T*
What happens when S is given S* as input?
This table embodies a contradiction.
|halts||if T does not halts on input S*
|fails to halts||if T halts on input S*
CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000