|
| Homework 10General Comments
- Problems are taken from the textbook unless otherwise noted.
- For full credit, provide context for each problem, show all calculations, and explain your work/answers.
- Numbers and/or algebra by themselves are not enough.
- You will lose a significant amount of credit if you do not show enough work/context for your answers.
- Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
- Homework assignments must be very neatly written or typeset
(e.g. using Word or OpenOffice).
- You must indicate any assistance you had on an assignment as specified on the Policies page.
Details| Problem | Points | Comments
|
|---|
| 4.2 | 5 | Make sure to do both parts! This problem is pretty easy. If you are having a difficult time with it, you probably need to re-read the chapter and pay closer attention to the examples.
| | 4.4 | 5 | Don't make this one harder than it is.
| | 4.6 | 6 | This one should be pretty easy.
| | 4.8 | 4 | (Bonus! You can skip this one if you would like.) 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.) There are many very straightforward functions that can work, but seeing what to do can be tricky.
| | 4.16 | 5 | Regular languages are closed under intersection. Use this and a TM from the chapter to show that A is decidable.
| | 4.24 | 5 | (Bonus! You can skip this one if you would like.) Make sure to do both parts!
| | Problem 1 below | 5 | Read the problem below! 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.
|
Problem 1
Let VERIFYTM = { ⟨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 VERIFYTM is undecidable.
More Hints
- If a problem asks to prove a language is decidable, you need to
provide a high-level description of a TM that decides the language.
- 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 EDFA is decidable. Exercise 4.10 uses this fact to construct a TM to decide the given language.
|
|
|