Overview / Logistics

In this homework we'll explore decidability: the property of a language that guarantees that it is both Turing recognizable and that it will never throw the Turing machine into an infinite loop. In the process, we'll also think about languages that are not decidable.

There are no JFLAP problems on this homework. You should submit a single typed document with the answers to each question. You can use Microsoft Word, LaTeX, or anything else you're comfortable with.

Problem 1 (3 Points)

Consider the following Turing machine M (Click here to download the JFLAP file)

Now consider a universal turing machine H that takes as input <M, s>, where <M> is a string encoding of another turing machine and s is an input, and H accepts if M halts on s and rejects if M loops on s (we know that such a machine can't exist, but for the purposes of this problem, we'll pretend that it does). Assuming a 6-tuple representation of a turing machine (Q, Σ, Γ, δ, q, F), where Σ is the input alphabet and Γ is the tape alphabet, devise examples of the following 3 inputs

1. An input where H accepts and M accepts s
2. An input where H accepts and M rejects s
3. An properly formatted input where H rejects (i.e. M is encoded properly in its string representation as a tuple)

You can encode a transition rule in string format as a tuple

which reads a machine in state q_i with an a at its head write a b to the tape, transitions to state q_j, and either moves left/stays/moves right.

---

Problem 2 (3 Points)

Prove that the language

B = { < M > | M is a DFA which doesn't accept any binary strings divisible by 3 }

Is decidable. For example, the machine below is in B, since it rejects everything except for the string 1, and 1 is not divisible by 3.

Hint: Recall that the language E_DFA(<M>), which accepts if the DFA M does not accept any strings, is decidable (see theorem 4.4 in the book). Use a decider for E_DFA as a subroutine to help you in this problem.

---

Problem 3 (3 Points)

Prove that the language

P = { < M > | M is a DFA over the alphabet Σ={(,)} that accepts at least one string with balanced parentheses }

is decidable. For example, the machine M below, which accepts all of the strings of the form ()()()..., is in P

Hint: Use the fact that the intersection of a context free language and a regular language is context free. Then use theorem 4.8 in the book that E_CFG is decidable.

---

Problem 4 (3 Points)

Show that for any infinite language L, L is decidable if and only if some Turing enumerator enumerates L in lexographic order. You may use a high level description of any Turing machines at play. Note that you will have to prove two directions for the if and only if

1. If some Turing enumerator enumerates L in lexographic order, then L is decidable
2. If L is decidable, then some Turing enumerator enumerates L in lexographic order

As a hint for the first direction, let's consider the language of binary strings with an even number of 0's. This language can be recognized by a DFA, so it's definitely decidable! Here are the first 20 strings that a turing enumerator for this language would print out if it did so in lexographic order

When creating a decider, you can't assume any knowledge of the language other than what the enumerator tells you, so you have to tie your hands behind your back and just look at the strings that come out of the enumerator to decide whether a string is in the language. For example, if you wanted to check if the string 1011 was in this language, how would you do so by just examining the above strings coming out in lexographic order? When would you know that you could reject this string?

---

Problem 5 (3 Points)

Show that every infinite Turing-recognizable language has an infinite decidable subset. An example of this is Hilbert's 10th problem, which is recognizable and undecidable, but we showed in the last problem set that the language of all univariate integer polynomials with integer roots is decidable, and that language is a subset of the original language.

Hint: Have a look at the proof for Theorem 3.21 (Pg. 153 Sipser 2nd edition) that a language is Turing-recognizable if and only if some enumerator enumerates it. Focus on the second part where we start with a recognizable language and construct an enumerator, then modify this construction to enumerate an infinite language of strings in lexographic order, which is decidable by appealing to your proof in the last problem. Even if you can't figure out the proof for the previous problem, you may use the result in this problem.

---

Problem 6 (3 Points)

Prove that the language

is decidable by coming up with a high level description of a machine that decides it.

Hint: Put yourself in a pumping mindset here, and argue that a DFA with k states rejects infinitely many strings if and only if it rejects a string with a length between k and 2k