General instructions

1. At the top of your solutions, be sure to write down the names of anyone you discussed this assignment with or any resources you used!

2. Please copy the description of the problem as well as your solution. 

3. Submit your written work through Gradescope. Refer to Tools for details on using both. 

You may find it useful that all problems from the Sipser's Theory of Computation (2nd edition) can be found here.

Exercises 

• From Sipser, 2nd edition (page 195):

  • 5.1

  • 5.2

  • 5.4

  • Show that if A is co-Turing-recognizable and A' ≤m A, where A' is the complement of A, then A is decidable.

  • Show that ALLTM = {<M> | L(M) = Σ*} is neither Turing-recognizable nor co-Turing-recognizable.

Problems 

• From Sipser, 2nd edition (page 195):

  • 5.13