Consider the following construction of a Turing machine: \On input w 1. Let n = jwj. 2. Create a two dimensional array of strings sm;j where 0 m n and 0 j 1. 3. For each 0 m n, initialize sm;0 to be the prex of w of length m and sm;1 to be the sux of w of length nm. In other words, w = sm;0sm;1 and jsm;0j = m, jsm;1j = n m. 4. For i = 1; 2; : : : 5. For k = 0; : : : ; i 6. Run M1 on smin (k;n);0 for (at most) i steps. 7. Run M2 on smin (k;n);1 for (at most) i steps. 8. If both simulations in steps 6 and 7 accept, accept." Can this construction be used to prove that the class of Turing-recognizable languages is closed under concatenation? Brie y justify your answer.

(c) Consider the following construction of a Turing machine On input w 1. Let n 2. Create a two dimensional array of strings smy where 0