0
Short Note on Rice theorem.

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M , 10M

Year: Dec 2015 , May 2015

0  upvotes
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.

0  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More