1. (Code as data) Consider the following description of a three-tape TM H. Algorithm: H((M, w)) Input : Encoding of a basic TM M and a string we {0, 1}* 1. Copy the the string w to tape 2. 2. Repeat the following three steps forever: 3. Simulate M for one step on tape 2. 4. Erase the contents of tape 3. Copy the contents of tape 2 to tape 3, and check if the substring 1010 appears on tape 3. If it does, accept. Otherwise, continue. 5. If M halts (in either an accept or reject state), reject. Otherwise, continue. (a) Let M be the following (uninteresting) TM. Is (M1,) E L(H)? Explain why or why not. Algorithm: M1(2) Input : String x {0,1}* 1. Write "010101 to the tape and reject. (b) Let M, be the following TM. Is (M2, 101) L(H)? Explain why or why not. Algorithm: M2(2) Input : String x {0, 1}* 1. Scan the input string x and (without writing anything) accept if the last symbol of x is 1. Otherwise, reject. (c) What is the language L(H) recognized by H? (d) Is H a decider for the language L(H)? Explain why or why not. 1. (Code as data) Consider the following description of a three-tape TM H. Algorithm: H((M, w)) Input : Encoding of a basic TM M and a string we {0, 1}* 1. Copy the the string w to tape 2. 2. Repeat the following three steps forever: 3. Simulate M for one step on tape 2. 4. Erase the contents of tape 3. Copy the contents of tape 2 to tape 3, and check if the substring 1010 appears on tape 3. If it does, accept. Otherwise, continue. 5. If M halts (in either an accept or reject state), reject. Otherwise, continue. (a) Let M be the following (uninteresting) TM. Is (M1,) E L(H)? Explain why or why not. Algorithm: M1(2) Input : String x {0,1}* 1. Write "010101 to the tape and reject. (b) Let M, be the following TM. Is (M2, 101) L(H)? Explain why or why not. Algorithm: M2(2) Input : String x {0, 1}* 1. Scan the input string x and (without writing anything) accept if the last symbol of x is 1. Otherwise, reject. (c) What is the language L(H) recognized by H? (d) Is H a decider for the language L(H)? Explain why or why not