Homework 10

Details

4.2
4.6
4.8
4.16
4.24
4.29
Let VERIFY_TM = { ‹M,D› | M is a TM which does D}. For instance, D might be "sorts a given list", or "finds the maximum clique in a given graph." Prove that VERIFY_TM is undecidable.

Hints:

To prove a set is countable, you can define a one-to-one function from elements of the set to the natural numbers. Notice I did not say that it has to be onto. (This is because if you can define a one-to-one mapping from a set to a subset of the natural numbers, clearly the set is no larger than the size of the natural numbers, so it must be countable.)
The solutions to 4.10, 4.12, and/or 4.14 might help you think about how to do several of these problems.
Use the theorems in the chapter. For instance (this is a random example which may or may not apply to any of the problems), Theorem 4.4 tells you that E_DFA is decidable. Exercise 4.10 uses this fact to construct a TM to decide the given language.
For problem 4.29:
- The symbol ∞ is in the alphabet. That is, k can be an integer or the ∞ symbol. For instance, ‹G,7› is in the language if L(G) contains exactly 7 strings, and ‹G,∞› is in the language if L(G) contains an infinite number of strings.
- You may use the result of exercise 4.11 if you think it will help.
- Knowing the pumping length of the language might be helpful.
- Two questions remain: Why does knowing the pumping length help, and can you determine it? (Hint: See the proof of the pumping lemma.)
For the VERIFY problem, assume it is decidable and use a TM that decides this to construct a TM to decide a language you know is undecidable--like one discussed in section 5.1.