Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

## Problem 1

Write an algorithm that takes two Turing machines,

*M*_{1}
and

*M*_{2}, as input and
returns a single Turing machine that does the same thing as
running

*M*_{1} and, if it halts, subsequently running

*M*_{2} starting with the same tape and tape reader position as

*M*_{1} halted in. So, fill in the ???? below:

**Input:** TM's *M*_{1} = (Q_{1},Σ_{1},Γ_{1},δ_{1},s_{1})
and
*M*_{2} =
(Q_{2},Γ_{1},Γ_{2},δ_{2},s_{2}),
where Q_{1} ∩ Q_{2} = ∅

**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

*M*_{2} must be

*Γ*_{1}, since it'll be reading as input the string
that

*M*_{1} leaves on the tape.
This algorithm will justify our use of the simple

*Machine
Schema* used in the lecture notes.