3. Consider the following computational problems ZTM-M) | M is a Turing machine and 0 E L(M) T2TM-1(M) I M is a Turing mlachine and | L(M)| 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 T2rM in order to define a genie-decider for ZrM. 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 z has length greater than 1, reject 2. If z = , reject. 3. If z = 0, accept. 4. Otherwise, simulate M on 0 If this simulation accepts, If it re 2. Ask the genie G about input 3. If the genie accepts, The key observations in the correctness proof of this construction, are that for any TM M, ir(M) E ZTW, then L(X) equals , and Mz accepts(M); . if M ZTM, then L(X) equals _-, and Mz rejects(M) Thus, L(Me)-I TM 3. Consider the following computational problems ZTM-M) | M is a Turing machine and 0 E L(M) T2TM-1(M) I M is a Turing mlachine and | L(M)| 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 T2rM in order to define a genie-decider for ZrM. 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 z has length greater than 1, reject 2. If z = , reject. 3. If z = 0, accept. 4. Otherwise, simulate M on 0 If this simulation accepts, If it re 2. Ask the genie G about input 3. If the genie accepts, The key observations in the correctness proof of this construction, are that for any TM M, ir(M) E ZTW, then L(X) equals , and Mz accepts(M); . if M ZTM, then L(X) equals _-, and Mz rejects(M) Thus, L(Me)-I TM