CSE 431: HW #2

Out: Tuesday, 16-Jan

Due: Tuesday, 23-Jan before class

Assignment

1. Decidability

   1. Prove that the language \(\mathrm{ALL}_{\mathsf{DFA}} = \left\{ \langle A \rangle \mid A \textrm{ is a } \mathsf{DFA} \textrm{ and } \mathcal{L}(A) = \Sigma^*\right\}\) is decidable.
   2. Prove that the language \(\mathrm{SUB}_{\mathsf{DFA}} = \left\{ \langle A,B\rangle : A \textrm{ and } B \textrm{ are } \mathsf{DFAs} \textrm{ and } \mathcal{L}(A) \subseteq \mathcal{L}(B) \right\}\) is decidable.

2. Undecidability

   Suppose that \(M\) is a Turing machine with set of states \(\mathcal{Q}\). Say that a pair of states \(q,q' \in \mathcal{Q}\) with \(q \neq q'\) is alternating if on every input to \(M\), it has the following behavior: If the state \(q\) is entered, then before it is entered again, \(M\) must enter the state \(q'\). Similarly, if \(q'\) is entered, then before it is entered again, \(M\) must enter the state \(q\).

   Consider the problem of determining whether a Turing machine \(M\) has a pair of alternating states. Formulate this problem as a language and show that it is undecidable.

3. Computable numbers

   Recall the definition of a computable number (Sipser 5.3).

   Consider Turing machines with alphabet \(\Sigma = \{0,1\}\) and tape alphabet \(\Gamma = \{0,1,␣\}\). Define the function \(F : \mathbb{N} \to \mathbb{N}\) as follows. For each value \(k\), consider all the \(k\)-state Turing machines that halt when started with a blank input tape. Let \(F(k)\) denote the maximum position of the tape head during any run of such a Turing machine when started on a blank input.

   Show that the function \(F\) is not computable.

Extra credit

1. Cardinality: For each of the following, say whether it is possible or not. If it is possible, describe a recipe for drawing them. If not, provide a proof that no such drawing exists.

   1. Is it possible to draw an uncountable number of circles in the plane such that none of them intersect? The circles can have any radius.

   2. Is it possible to draw an uncountable number of 'B's in the plane wuch that none of them intersect? (You may assume that the line segment and the two "bumps" are simply one-dimensional curves. The copies can be rotated or scaled.)

      

2. Decidability: Show that the problem of determining whether a \(\mathsf{CFG}\) (see Sipser 2.1 to recall the definition of a context-free grammar) generates all strings of the form \((01)^*\) is decidable. (In other words, whether it generates all the strings \(\{\varepsilon, 01, 0101, 010101, \ldots\}\). It is OK if the \(\mathsf{CFG}\) generates other strings beside these as well.)

3. Computability:

   1. Show that \(F\) from problem (3) above grows faster than any computable function in the following sense: If \(G : \mathbb{N} \to \mathbb{N}\) is any computable function, then there is some \(k \geq 1\) such that \(F(n) > G(n)\).

   2. Is there a computable function \(G\) such that \(G(n) > F(n)\) for infinitely many values of \(n\)? Give an example or show that no such \(G\) exists.