Tag Info

Rice's Theorem states that any (non-trivial) property of Turing machines is undecidable.

## Rice's theorem :

Let $L = \{ \langle M \rangle \mid L(M) \text{ has some property } P \}$ where :

1. $P$ is non-trivial, i.e. there exists at least one machine $M_1$ such that $\langle M_1 \rangle \in L$, and at least one machine $M_2$ such that $\langle M_2 \rangle \not \in L$.

2. $P$ is indeed a property of the language of TMs, i.e. whenever $L(M_a) = L(M_b)$, we have $\langle M_a \rangle \in L$ if and only if $\langle M_b \rangle \in L$.

Then, $L$ is undecidable.

## What is a property?

A "property" is simply a subset of languages in $RE$ -- the set of all the languages that "satisfy" that property. A non-trivial property $P$ is a non-empty set $P$ which is strictly contained in $RE$, that is $\emptyset \subset P\subset RE$. It means there is at least one RE language that doesn't satisfy $P$, and at least one RE language that does satisfy it.

Example:

The property: "the language is finite."
Formal definition: $P = \{ L(M) \mid |L(M)|<\infty\}$.

The property: "The language can be recognized by a TM". Formally: $P=\{ L \mid \exists M \text{ s.t. } L=L(M)\}$. This property is trivial: in fact $P=RE$, that is, ALL RE languages satisfy it.

The property: "The language has a reduction from the non-halting problem". Formally: $P = \{ L \mid \overline{HP} \le L\} \cap RE$. This property is trivial: in fact, $P=\emptyset$.