Question 6.9: Use the recursion theorem to give an alternative proof of Ri...
Use the recursion theorem to give an alternative proof of Rice’s theorem in Problem 5.28.
Assume for the sake of contradiction that some TM X decides a property P, and P satisfies the conditions of Rice’s theorem. One of these conditions says that TMs A and B exist where 〈A〉 ∈ P and 〈B〉 ∉ P. Use A and B to construct TM R:
R = “On input w:
1. Obtain own description 〈R〉 using the recursion theorem.
2. Run X on 〈R〉.
3. If X accepts 〈R〉, simulate B on w.
If X rejects 〈R〉, simulate A on w.”
If 〈R〉 ∈ P, then X accepts 〈R〉 and L(R) = L(B). But 〈B〉 ∉ P, contradicting 〈R〉 ∈ P, because P agrees on TMs that have the same language. We arrive at a similar contradiction if 〈R〉 ∉ P. Therefore, our original assumption is false.
Every property satisfying the conditions of Rice’s theorem is undecidable.