Q1.
(1) It is decidable through a TM that rejects all strings.
(2) It is decidable through a TM that accept any string.
(3) Suppose ∅ not in P. If ∅ in p, we can prove L(complement p) is
undecidable, and then Lp = (complement L(complement p)) is also undecidable. Now, we prove we can reduce ATM to LP. Because P is not empty, there is one TM M0 where L(M0) ∈ P, the reduction map ⟨M,w⟩ from ATM to ⟨F⟩. F is a TM and
F = “On input s Run M on w
If M accept w then run M0 on s and F accept s if and only if
M0 accepts s.”
If M doesn’t accept w then F doesn’t accept s.”
From above reduction, we can see that if M accepts w, then L(M) = L(M0) ∈P and if M doesn’t accept w, then F accepts ∅ , L(F)=∅ which doesn’t belong to P, so it reduces ATM to LP.
Q2.
Suppose the symbols in Σ are a, b. We can easily modify following grammar to include more symbols.
S A B T N
1.
2. 3. 4. 5.
-> AT | TA | BNB
-> a | b | Aa | Ab
-> a | b | epsilon | Ba | Bb
->aTa|bTb|# -> aTb | bTa
S will derive the language {C#DR : C, D ∈Σ∗ and C does not yield D}
A derive the language Σ+
B derive the language Σ∗
T derive the language {D#DR : D ∈Σ∗ }
N derive the language {xD#DRy : D ∈Σ∗ x !=y}
x∈Σ y∈Σ
Q3.
Assume that K(x) is computable. And the program that computes the K(x) has size C.
Now consider the program G(n): For each x in {0, 1}n, if x is the first string with K(x)>=n, print x out and halt.
It has size C + log(n). From definition of K(x), we have K(x) <= C + log(n). But for large enough n, we have C + log(n) < n <= K(x), which is a contradiction.