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

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} . "\)

Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet \(\\{0,1\\}\). A a. \(\\{w \mid w\) contains an equal number of 0 and 1 s \(\\}\) b. \(\\{w \mid w\) contains twice as many 0 s as 1 s \(\\}\) c. \(\\{w \mid w\) does not contain twice as many \(0 \mathrm{~s}\) as $1 \mathrm{~s}\\}$

Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning. a. Can a Turing machine ever write the blank symbol \(\lrcorner\) on its tape? b. Can the tape alphabet \(\Gamma\) be the same as the input alphabet \(\Sigma\) ? c. Can a Turing machine's head ever be in the same location in two successive steps? d. Can a Turing machine contain just a single state?

Let \(c_{1} x^{n}+c_{2} x^{n-1}+\cdots+c_{n} x+c_{n+1}\) be a polynomial with a root at \(x=x_{0}\). Let \(c_{\max }\) be the largest absolute value of a \(c_{i}\). Show that $$ \left|x_{0}\right|<(n+1) \frac{c_{\mathrm{max}}}{\left|c_{1}\right|} $$

(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.