1. (More closure properties) (a) Given Turing machines M1, M2, give a high-level description of a nondeterministic (multi- tape) TM recognizing L(M1), L(M2). Note: It is possible to do this with a deterministic TM, but we want to give you practice with the concept of nondeterminism. So your solution must use an NTM's ability to nondeterministically guess in a meaningful way. (b) Explain why part (a) implies that the Turing-recognizable languages are closed under concate- nation. (c) Given a Turing machine M, give a high-level description of a nondeterministic (multi-tape) TM recognizing (L(M))*. Again, your solution must use nondeterminism in a meaningful way. (d) Explain why part (b) implies that the Turing-recognizable languages are closed under star. (e) Explain (briefly) how you would modify your previous constructions and their analyses to show that the decidable languages are closed under concatenation and star. Hint: Recall that a nondeterministic TM is a decider if it halts on every input, on every computation branch. The class of languages decided by NTMs is exactly the class of decidable languages. 1. (More closure properties) (a) Given Turing machines M1, M2, give a high-level description of a nondeterministic (multi- tape) TM recognizing L(M1), L(M2). Note: It is possible to do this with a deterministic TM, but we want to give you practice with the concept of nondeterminism. So your solution must use an NTM's ability to nondeterministically guess in a meaningful way. (b) Explain why part (a) implies that the Turing-recognizable languages are closed under concate- nation. (c) Given a Turing machine M, give a high-level description of a nondeterministic (multi-tape) TM recognizing (L(M))*. Again, your solution must use nondeterminism in a meaningful way. (d) Explain why part (b) implies that the Turing-recognizable languages are closed under star. (e) Explain (briefly) how you would modify your previous constructions and their analyses to show that the decidable languages are closed under concatenation and star. Hint: Recall that a nondeterministic TM is a decider if it halts on every input, on every computation branch. The class of languages decided by NTMs is exactly the class of decidable languages