- 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*ishalts 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?

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