Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Write an algorithm that takes two Turing machines, M1 and M2, as input and returns a single Turing machine that does the same thing as running M1 and, if it halts, subsequently running M2 starting with the same tape and tape reader position as M1 halted in. So, fill in the ???? below:
Input: TM's M1 = (Q1111,s1) and M2 = (Q2122,s2), where Q1 ∩ Q2 = ∅
Output: TM M such that $(s_1,\lambda,w_1,w_2\cdots w_k) \Rightarrow_{M_1}^* (h,x,y,z)$ and $(s_2,x,y,z) \Rightarrow_{M_2}^* (h,x',y',z')$ if and only if $(s,\lambda,w_1,w_2\cdots w_k) \Rightarrow_{M}^* (h,x',y',z')$, where $s$ is the start state of $M$
Notice that the input alphabet for M2 must be Γ1, since it'll be reading as input the string that M1 leaves on the tape. This algorithm will justify our use of the simple Machine Schema used in the lecture notes.