Problem 1

Write an algorithm that takes two Turing machines, M₁ and M₂, as input and returns a single Turing machine that does the same thing as running M₁ and, if it halts, subsequently running M₂ starting with the same tape and tape reader position as M₁ halted in. So, fill in the ???? below:

Input: TM's M₁ = (Q₁,Σ₁,Γ₁,δ₁,s₁) and M₂ = (Q₂,Γ₁,Γ₂,δ₂,s₂), where Q₁ ∩ Q₂ = ∅
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₂ must be Γ₁, since it'll be reading as input the string that M₁ leaves on the tape. This algorithm will justify our use of the simple Machine Schema used in the lecture notes.

Problem 2

Consider the two machines below: $T$ and $M$. a. Modify the picture below to show how the schema >$T \longrightarrow M$ gets converted by your algorithm into a single machine. b. Write down the sequence of configurations for the computation of the combined machine on input $ba$. c. Circle the supsequence of configurations that would correspond to the computation of $M$ as a Bookish TM on input $ba$.