Question

Rice’s theorem. Let P be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine’s language has property P is undecidable. In more formal terms, let P be a language consisting of Turing machine descriptions where P fulfils two conditions. First, P is nontrivial—it contains some, but not all, TM descriptions. Second, P is a property of the TM’s language—whenever $L\left(M_1\right)=L\left(M_2\right)$, we have if and only iff . Here, $M_1$ and $M_2$ are any TMs. Prove that P is an undecidable language.

Short answer

It is proved P is undecidable.

Step-by-step solution

Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Proving   as undecidable

Let us assume P is a decidable language and let Turing Machine $R_P$ that decides P

.

We will design Turing Machine s that will decide $A_{TM}$by the use of$R_P$. First, let T' be a Turing Machine that always rejects for any input.

This means: $L\left(T\text{'}\right)=\varnothing$.

For clarity we will assume that so that we not proceed with $\overline{P}$ instead of P if . Because P is not trivial, so there exists a Turing Machine T with.

Now we will design Turing Machine S using $R_P$ because $R_P$

s= on input$\left(M,w\right)$

• Use M and w to construct the following TM $M_W$.

$M_w$=on input x $M_w=oninputx$$M_w=oninputx$

Run M on w .

If it halts and rejects, reject.

If it accepts, proceed to stage 2.

Run T on x . If it accepts, accept.

• Use TM$R_P$to determine whether $M_w\in P$.

If YES, accept

Else

If NO, reject.

Turing Machine $M_w$ runs T if M accepts w .

Hence

• $L\left(M_W\right)=L\left(T\right)$if M accepts w
• If reject then $L\left(M\right)=\varnothing$.

Therefore, $M_W\in P$if and only if M accepts w.

But $A_{TM}$ is undecidable, so s which is made similar to $R_P$ cannot decide P .

Thus, P is undecidable.