Problem 1. Complete the TopHat worksheet titled Spring 2020 HW6.1. There are a total of 10 questions, each worth 2 points.
Problem 2. Consider the following algorithm describing the TM M1:
Input: hDi, the encoding of a DFA D.
1. Simulate D on input ε.
2. if(D accepts input ε)
3. Accept hDi.
5. else
6. Reject hDi.
Using M1, prove that L1 = {hDi | hDi is the encoding of a DFA is Turing decidable.
Problem 3.
Prove the following theorem:
If language L is undecidable and Turing recognizable, then L 6≡m L.
Problem 4.
Recall the following decision problem ALLTM:
ALLTM:
INSTANCE: hMi, the encoding of a Turing machine.
QUESTION: Is L(M) = Σ∗? (i.e., does M accept every input?)
Consider the function: f1(hM,wi) = hAoNM,wi
where AoNM,w is the All-or-Nothing machine as defined in lecture. Prove that ATM ≤m ALLTM via this function f1. Conclude that ALLTM is undecidable.
