Let $B=\left\\{\left\langle M_{1}\right\rangle,\left\langle M_{2}\right\rangle, \ldots\right\\}$ be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions such that every machine described in \(B\) has an equivalent machine in \(C\) and vice versa.

(a) For any two decidable languages \(L_{1}\) and \(L_{2}\), let \(M_{1}\) and \(M_{2}\) be the TMs that decide them. We construct a $\operatorname{TM} M^{\prime}\( that decides the union of \)L_{1}\( and \)L_{2}$ : "On input w: 1\. Run \(M_{1}\) on \(w\). If it accepts, accept. 2\. Run \(M_{2}\) on \(w\). If it accepts, accept. Otherwise, reject." \(M^{\prime}\) accepts \(w\) if either \(M_{1}\) or \(M_{2}\) accepts it. If both reject, \(M^{\prime}\) rejects.

In Theorem \(3.21\), we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn't we use the following simpler algorithm for the forward direction of the proof? As before, \(s_{1}, s_{2}, \ldots\) is a list of all strings in \(\Sigma^{*}\). \(E={ }^{*}\) Ignore the input. 1\. Repeat the following for \(i=1,2,3, \ldots\) 2\. Run \(M\) on \(s_{i}\). 3\. If it accepts, print out \(s_{i} . "\)

The language \(A\) is one of the two languages \(\\{0\\}\) or \(\\{1\\} .\) In either case, the language is finite and hence decidable. If you aren't able to determine which of these two languages is \(A\), you won't be able to describe the decider for \(A\). However, you can give two Turing machines, one of which is \(A\) 's decider.

Show that the collection of decidable languages is closed under the operation of A. union. d. complementation. b. concatenation. e. intersection. c. star.

Show that the collection of Turing-recognizable languages is closed under the operation of \(A_{\text {a. union. }}\) d. intersection. b. concatenation. e. homomorphism. c. star.