Homework Exercise 3, Due Feb 16

For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks *will* be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

1. Prove that ~E_TM (the complement of E_TM) is recognizable.

2. Prove that the following language is undecidable -- you may make use of any of the undecidable languages from class. B_TM = { < M > : M is a TM that halts on input epsilon } (Remember that "on input epsilon" means "when started with a blank input tape".)