0
Short Note on Rice theorem.

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M , 10M

Year: Dec 2015 , May 2015

0

Let C be a set of languages. Consider the language $L_c$ defined as follows

$L_c = {{M} | L {M} ∈ C}.$

Then either $L_c$ is empty, or it contains the descriptions of all Turing machines, or it is undecidable.

Proof:

• Suppose towards a contradiction that for same class C the language $L_c$ is not empty, it does not contain the descriptions of all Turing machines, and it is decidable.

• Then $L_c$ is also not empty, not containing all Turing machines, and decidable.

• Suppose that ∅ 6∈ C, otherwise apply the argument below to $L_c$ instead of $L_c$

• Let $M_{in}$ be a machine such that $M_{in}$ is in $L_c$.

• We will show that the Acceptance problem is decidable, and so we will reach a contradiction.

• Given an input ({M}, w) for the Acceptance problem, we constract a new Turing machine M_w that does the following: on input x, $M_w$ first simulates the behaviour of M on input w and

• If M on input w loops, then so does $M_w$;
• If M on input w rejects, then so does $M_w$;
• If M on input w accepts, then M_w continues with a simulation of M_in on input x.
• In summary:

• If M accepts w, then $M_w$ behaves like $M_{in}$, and $M_w$ accepts an input x if and only if $M_{in}$ does. In other words, $L(M_w) = L(M_{in}) ∈ C \ \ \ \ and \ \ so \ \ {M_w} ∈L_c$;

• If M does not accept w, then $M_w$ does not accept any input, and L $(M_w) = ∅ ∈ C$, which implies ${M_w} ∈ L_c$.

• We have proved that ({M}, w) ∈ A if and only if ${M_w} ∈ L_c$, and so A would be decidable if $L_c$ were decidable. We have reached a contradiction.