Assignment 9

1. Consider the language \(\textrm{ALL}_\textrm{DFA}\) consisting of the string representations of all DFAs \(D\) such that \(L(D) = \Sigma^*\) is the language of all strings in the alphabet (the alphabet defined by that \(D\)). Show that this is a decidable language.
2. Consider the language \(L = \left\{\langle M, N\rangle\mid M,N\textrm{ are TMs and }L(M) \cup L(N) = \emptyset \right\}\).
   1. Show that \(L\) is not decidable.
   2. Show that \(L\) is co-Turing-recognizable.
   3. Show that \(L\) is not Turing-recognizable.
3. Consider the language \(L = \left\{\langle M, w\rangle\mid M\textrm{ is TM and does not halt on }w\right\}\). Determine which of the following classifications is the correct one for \(L\):
   • decidable
   • Turing-recognizable but not decidable
   • co-Turing-recognizable but not decidable
   • neither Turing-recognizable nor co-Turing-recognizable.
4. True or False (provide proof or counter-example as appropriate):
   1. If \(A\subset B\) are two languages, then if \(A\) is decidable then \(B\) is also decidable.
   2. If \(A\subset B\) are two languages, then if \(B\) is decidable then \(A\) is also decidable.
5. Suppose \(A\) is a decidable language, and consider the language \(L_A=\left\{\langle M, w\rangle\mid M\textrm{ is a TM and it accepts }w\textrm{ and what is left on the tape at that point is an element of }A\right\}\). For each of the following determine if it is true or false. Provide proof or counter-example as appropriate.
   1. For every decidable language \(A\), we have \(L_A\) is Turing-recognizable.
   2. For every decidable language \(A\), we have \(L_A\) is decidable.
   3. There is a decidable language \(A\) for which \(L_A\) is decidable.