Question

Use the recursion theorem to give an alternative proof of Rice’s theorem in Problem 5.28.

Short answer

Answer:

Rice’s Theorem is proved.

Step-by-step solution

Rice Theorem

Let’s first recall the Rice’s Theorem which was in Problem 5.28.

Let be a language consisting of Turing machine descriptions, then P must fulfil the following conditions:

P is nontrivial—it contains some, but not all, TM descriptions.

P is a property of the TM’s language—whenever we have

$<M1>\in Piff<M_2>\in P.$Here, $M_{1}and{M}_{2}areanyTMs.$

Proving rice Theorem

Now, let us assume as Turing Machine that is decider of P and P satisfy both the conditions of Rice’s Theorem which is mentioned above. The second condition says that there are two Turing Machine M₁ and M₂ , where M₁ $\in$P and M₂ $€$P.

Now we will use M₁ and M₂ to construct a Turing Machine R as follows:

R=on input(w)

• Obtain own description using recursion theorem.
• Run X on <R>
• If X accepts <R> , run M₂ on w

Else

If rejects , run M₁ on w

<R> $\in$P, then X will accepts =<R> and L(R) = L($M_2$)

But since, <B> $€$P so this makes as contradict statement. This is due to the fact that P will agree on Turing Machines that have same language.

Also, <R> $€$P can also be conclude from above. This shows our assumption was wrong.

So every property which satisfies Rice’s Theorem are undecidable.