Homework Exercise 4

Due: by 6pm on Wed 27 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 for all decidable languages L, L ≤m {00,11} (over alphabet Σ = {0,1}).
    Hint: Take the time to write down precisely what it means for L to be decidable, and what it means to show "L ≤m {00,11}".

  2. Prove or disprove that ETM ≤m ATM.

  3. Prove that REGULARTM is unrecognizable, by making appropriate use of ≤m.