[SOLVED] : CS 3800 HW3

CS 3800 2016-10-27. Return this single, two-sided sheet. Your name:

1. 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 .
2. 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 23 windows which are not consistent with Ms 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.
3. 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.)