Theorem

L = {<m> | L (M) ∈ P} is undecidable when p, a non-trivial property of the Turing machine, is undecidable.

If the following two properties hold, it is proved as undecidable −

Property 1 − If M1 and M2 recognize the same language, then either <m1> <m2> ∈ L or <m1> <m2> ∉ L

Property 2 − For some M1 and M2 such that <m1> ∈ L and <m2> ∉ L

Proof −

Let there are two Turing machines X1 and X2.

Let us assume X1 ∈ L such that

L(X1) = φ and <x2> ∉ L.

For an input ‘w’ in a particular instant, perform the following steps −

• If X accepts w, then simulate X2 on x.

• Run Z on input <w>.

• If Z accepts <w>, Reject it; and if Z rejects <w>, accept it.

If X accepts w, then

L(W) = L(X2) and <w> ∉ P

If M does not accept w, then

L(W) = L(X1) = φ and <w> ∈ P

Here the contradiction arises. Hence, it is undecidable.