3. Consider the following computational problems zrM-{ M) | M is a Turing machine and 0 L (M)) T2TM(M) |M is a Turing machine and |L(M)l 2 2) Complete the proof that ZTM reduces to T2TM by filling in the appropriate blanks Proof: We will use access to a genie G for T2TM in order to define a genie-decider for ZTM. Define Mz-"On input M) : 0. Check that input is valid encoding of a Turing machine. If not, reject. 1. Build a new TM X (over the alphabet $0,1]) defined as follows: X "On input x: 1. If x has length greater than 1, reject. 2. If reject. 3. If x= 0, accept. 4. Otherwise, simulate M on 0. If this simulation accepts, ; If it rejects, 2. Ask the genie G about input 3. If the genie accepts, ; If it rejects, The key observations in the correctness proof of this construction, are that for any TM M if M) E ZT"M , then L(X) equals . if M ZTM, then L(X) equals and Mz accepts M); , and Mz rejects (M) Thus, L(Mz) -ZTM- 3. Consider the following computational problems zrM-{ M) | M is a Turing machine and 0 L (M)) T2TM(M) |M is a Turing machine and |L(M)l 2 2) Complete the proof that ZTM reduces to T2TM by filling in the appropriate blanks Proof: We will use access to a genie G for T2TM in order to define a genie-decider for ZTM. Define Mz-"On input M) : 0. Check that input is valid encoding of a Turing machine. If not, reject. 1. Build a new TM X (over the alphabet $0,1]) defined as follows: X "On input x: 1. If x has length greater than 1, reject. 2. If reject. 3. If x= 0, accept. 4. Otherwise, simulate M on 0. If this simulation accepts, ; If it rejects, 2. Ask the genie G about input 3. If the genie accepts, ; If it rejects, The key observations in the correctness proof of this construction, are that for any TM M if M) E ZT"M , then L(X) equals . if M ZTM, then L(X) equals and Mz accepts M); , and Mz rejects (M) Thus, L(Mz) -ZTM