Assignment 1:
Reading Assignments:
Sipser's Chapters 3 and 7.
- 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.
- Problem 7.19.
- Problem 7.22.
- Problem 7.23.
- Problem 7.24.
- Problem 7.27.