Assignment 1:

Reading Assignments: Sipser's Chapters 3 and 7.

1. Show that all Turing recognizable laguages (or r.e. sets) can be accepted by a Turing machine with only 2 nonaccepting states and one accepting state.
2. Problem 7.19.
3. Problem 7.22.
4. Problem 7.23.
5. Problem 7.24.
6. Problem 7.27.