CS 3800 2016-10-27. Return this single, two-sided sheet. Your name:
- In this problem you will show that you cannot decide anything about the language of Turing machines. Formally, let P be a set of languages over the alphabet Σ = {0,1}. Let LP := {M : M is a TM and L(M) ∈ P}.Prove that
(1) If LP = ∅ then LP is decidable.
(2) If LP = Σ∗ then LP is decidable.
(3) In all other cases, LP is undecidable. For this proof you must reduce ATM to LP . - In this problem you will fill the main missing detail of the proof that there is no decider for the language of CFG which derive Σ∗. Let M be a Turing machine with states Q and tape alphabet Γ. Let Σ = Q Γ, and # ̸∈ Σ. Let (ai,bi,ci;di,ei,fi) : i = 1,2,…,t be the t 2×3 windows which are not consistent with M’s transitions, as in the result about locality of computation.Give a CFG for the language {C#DR : C, D ∈ Σ∗ and C does not yield D}, where DR is the reverse of D. For each of the variables in your grammar, give the language it derives.
- Show that K(x) is not computable. (Recall that a function is computable if there exists a TM that started on an input for the function, always stops with the output of the function on the tape.)