Rice's Theorem in Theory of Computation

In this article, we have explained Rice's Theorem in Theory of Computation and presented an application of the theorem as well. It is used to identify Undecidable Languages.

Table of contents:

  1. Definition of Rice's Theorem
  2. Proof of Rice's Theorem

Pre-requisite: Undecidability in ToC

Let us get started with Rice's Theorem in Theory of Computation.

Definition of Rice's Theorem

Let T be the set of binary encodings of all Turing Machines.

T = {(M) : M is a Turing Machine with input alphabet {0, 1}}.

Rice Theorem states that:

If P is a subset of T such that:

  1. P != EMPTY that is there exists a Turing Machine M such that (M) is a subset of P.
  2. P is a proper subset of T that is there exists a Turing Machine N such that (N) is not a subset of P
  3. For two Turing Machines M1 and M2 with L(M1) = L(M2), then:

3.1. Either both (M1) and (M2) are in P
3.2. Or Both are not in P.

If the above conditions hold, then the Language P is undecidable.

If you do not know the meaning of Undecidable in context of Theory of Computation or need to refresh your memory, go through this article.

Three languages that satisfy the conditions in Rice's Theorem are:

  • P1 = { (M) : M is a Turing Machine and e belongs to L(M) }
  • P2 = { (M) : M is a Turing Machine and L(M) = {1011, 001100}}
  • P3 = { (M) : M is a Turing Machine and L(M) is a regular Language}.

Based on Rice's Theorem, all three languages P1, P2 and P3 are Undecidable Languages.

Therefore, Rice's theorem is used to find Language that are undecidable.

Proof of Rice's Theorem

To prove Rice's Theorem, you can follow the following steps:

  • Step 1: Prove Halting Problem is undecidable. This is a well known problem and is used as an example of a problem that cannot be solved by a Turing Machine.
  • Step 2: Proof by contradiction: Assume P is a decidable language and P is the Halting Language (corresponding to Halting Problem). P satisfies the conditions in Rice's Theorem.
  • Step 3: You will arrive at a result that P is decidable if and only if P' is decidable.
  • Step 4: This contradicts Step 1 and hence, cannot be true.

This proves Rice Theorem.

With this article at OpenGenus, you must have a strong idea of Rice's Theorem in Theory of Computation and how to apply it in problems.