Question: Short Note on Rice theorem.
0

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M , 10M

Year: Dec 2015 , May 2015

ADD COMMENTlink
modified 3.0 years ago  • written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
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.

ADD COMMENTlink
written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.