Reduction Problem

3. Consider the following computational problems ?yM = {?M) | M is a Turing machine and 0 E L(M)) T2TM-t(M) | M is a Turing machine and IL(M)2 2} Complete the proof that ZTM reduces to T2rM 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 r has length greater than 1, reject. 2. If -e, 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, o if (M) ZTM, 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 ?yM = {?M) | M is a Turing machine and 0 E L(M)) T2TM-t(M) | M is a Turing machine and IL(M)2 2} Complete the proof that ZTM reduces to T2rM 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 r has length greater than 1, reject. 2. If -e, 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, o if (M) ZTM, then L(X) equals if ?M) ZTM, then L(X) equals and Mz accepts ?M); and Mz rejects (M). Thus, L(Mz) -ZTM