Computer Science 4602, Fall 2018
Assignment 4

Exercises are from Sipser, third edition, beginning 187 for Chapter 3 and page 210 for Chapter 4.

1. 3.15(d, e)
2. 3.22
3. Prove that every finite language is Turing-decidable (computable).
4. Are all infinite languages uncomputable? Explain why or why not.
5. 4.3
6. 4.30
   (Hint: Write a program that takes integer inputs (so its input alphabet consists of decimal digits). On input i, it finds M_i and runs it on input i. What can your program do to ensure that your program does not compute the same language as M_i? Remember that M_i is guaranted to be a decider.
7. 5.4
8. 5.23
9. 5.30(b, c)
10. 5.31