• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Exercise 3

Due: by 6pm on Wed 13 Feb
Worth: 1.5%

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 ε }

   (Remember that "on input ε" means "when started with a blank input tape".)