0 1 10 000 0SS 42 93 A5 SolutionWe use a proof by contradict

Solution

We use a proof by contradiction. Suppose ATM is decided by some TM H, so H accepts hM, wi if TM M accepts w, and H rejects hM, wi if TM M doesn’t accept w. hM, wi H accept reject Define another TM D using H as a subroutine. H D hM,hMii accept reject hMi accept reject So D takes as input an encoded TM hMi, then feeds hM,hMii as input into H, and finally outputs the opposite of what H outputs. What happens when we run D with input hDi? Note that D accepts hDi iff D doesn’t accept hDi, which is impossible. Thus, ATM must be undecidable. Complete Proof: Suppose there exists a TM H that decides ATM. TM H takes input hM, wi, where M is a TM and w is a string. If TM M accepts string w, then hM, wi ATM and H accepts input hM, wi. If TM M does not accept string w, then hM, wi 6 ATM and H rejects 3 input hM, wi. Consider the language L = { hMi | M is a TM that does not accept hMi }. Now construct a TM D for L using TM H as a subroutine: D = “On input hMi, where M is a TM: 1. Run H on input hM,hMii. 2. If H accepts, reject. If H rejects, accept.” If we run TM D on input hDi, then D accepts hDi if and only if D doesn’t accept hDi. Since this is impossible, TM H must not exist, so ATM is undecidable