# Rice's Theorem in Theory of Computation

Get FREE domain for 1st year and build your brand new site

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:

- Definition of Rice's Theorem
- 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:

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

3.1. Either both (M_{1}) and (M_{2}) 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:

- P
_{1}= { (M) : M is a Turing Machine and e belongs to L(M) } - P
_{2}= { (M) : M is a Turing Machine and L(M) = {1011, 001100}} - P
_{3}= { (M) : M is a Turing Machine and L(M) is a regular Language}.

Based on Rice's Theorem, all three languages P_{1}, P_{2} and P_{3} 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.