[SOLVED] CSE396-Assignment 6

Description

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 M₁:

Input: hDi, the encoding of a DFA D.

1. Simulate D on input ε.
2. if(D accepts input ε)
3. Accept hDi.
4. else
5. Reject hDi.

Using M₁, prove that L₁ = {hDi | hDi is the encoding of a DFAis Turing decidable.

Problem 3. (10 points)

Prove the following theorem:

If language L is undecidable and Turing recognizable, then L 6≡_m L.

Problem 4. (15 points)

Recall the following decision problem ALL_TM:

ALL_TM:

INSTANCE: hMi, the encoding of a Turing machine.

QUESTION: Is L(M) = Σ^∗? (i.e., does M accept every input?)

Consider the function: f₁(hM,wi) = hAoN_M,wi

where AoN_M,w is the All-or-Nothing machine as defined in lecture. Prove that A_TM ≤_m ALL_TM via this function f₁. Conclude that ALL_TM is undecidable.