CSE 396 – Assignment 6 Solved

Description

In lecture we have concluded our discussion on computability and with it have moved into the realm of problems that are always decidable. This assignment touches on a number of the bits we saw during the exploration of the computability theory with a focus on some of the main theorems that tied everything together. Many-one reductions were a big part of our discussion and enabled us to show that many of the problems we were studying that asked about the behavior of a TM algorithm were undecdiable problems [of varying degrees].

Problem 1.  Complete the TopHat worksheet

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.

Prove the following theorem:

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

Problem 4.

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.