Rice's Theorem

computation languages

Definition

Rice's Theorem

Language Version
Fix an alphabet $\Sigma$. Let ${\mathrm{RE}}_{\Sigma }$ be the set of recursively enumerable languages over $\Sigma$.
For every non-trivial extensional language property $\mathcal{E}\subseteq {\mathrm{RE}}_{\Sigma }$, the code language

$$L_{\mathcal{E}}=\{⟨M⟩\mid L(M)\in \mathcal{E}\}$$

is undecidable.

Function Version
Fix a type/signature $\tau$ (e.g. ${\mathbb{N}}^k\to \mathbb{N}$ or ${\Sigma }^{\ast }\to {\Sigma }^{\ast }$). Let ${\mathrm{Comp}}_{\tau }$ be the class of (partial) Turing-computable functions of type $\tau$.
For every non-trivial extensional function property $\mathcal{F}\subseteq {\mathrm{Comp}}_{\tau }$, the code language

$$L_{\mathcal{F}}=\{⟨M⟩\mid F(M)\in \mathcal{F}\}$$

is undecidable.

Intuition

Rice’s theorem separates three levels:

1. a machine $M$
2. the language $L(M)$ accepted by $M$
3. the code $⟨M⟩$ that describes $M$

A language property $\mathcal{E}$ is extensional if it depends only on the language, not on the specific machine. So if two machines accept the same language, then either both satisfy $\mathcal{E}$ or neither does.

What is $\mathcal{E}$?

$\mathcal{E}$ is the set of all recursively enumerable languages that have the property in question.

For example, if the property is “being finite”, then $\mathcal{E}$ is the set of all finite recursively enumerable languages.

The theorem then turns the property into a language of codes:

$$L_{\mathcal{E}}=\{⟨M⟩\mid L(M)\in \mathcal{E}\}$$

This is the set of all machine codes whose accepted languages have property $\mathcal{E}$. In other words, the decision problem asks whether a given code describes a machine whose language has the property.

The property is trivial if every recursively enumerable language has it, or if none does. Rice’s theorem excludes these cases. It says that every non-trivial extensional language property gives an undecidable code language.

Scope

Scope

Rice’s theorem (language version) applies to extensional language properties of languages (e.g. emptiness, finiteness, decidability, membership of a fixed word).
Intensional language properties of recognisers/encodings are not covered.

Examples

Examples: Language version

More than five words

It is not decidable whether a given TM accepts more than five words.

Let $\mathcal{E}=\{L\mid |L|>5\}$. This property is extensional and non-trivial, since some r.e. languages satisfy it and some do not.

Explanation: The property depends only on the accepted language. One language with more than five words has it, and one language with five or fewer words does not. Therefore, Rice’s theorem applies, and thus it is undecidable.

Finite language

It is not decidable whether a given TM accepts only finitely many words.

Let $\mathcal{E}=\{L\mid L\text{ is finite}\}$. This property is extensional and non-trivial.

Explanation: The property depends only on the accepted language. Some recursively enumerable languages are finite, so $\mathcal{E}$ is not empty. Some recursively enumerable languages are infinite, so $\mathcal{E}$ does not contain all r.e. languages. Therefore, $\mathcal{E}$ is neither empty nor all of ${\mathrm{RE}}_{\Sigma }$. Therefore, Rice’s theorem applies, and thus it is undecidable.

Non-empty language

It is not decidable whether a given TM accepts any word at all.

Let $\mathcal{E}=\{L\mid L\ne \varnothing \}$. This property is extensional and non-trivial.

Explanation: The property depends only on the accepted language. The empty language does not have it, while any non-empty recursively enumerable language does. Therefore, Rice’s theorem applies, and thus it is undecidable.

Examples: Function version

Same function as $\mathbf{Pr}(P_1^1,S\circ P_2^3)$

It is not decidable whether a given TM computes the same function as $\mathbf{Pr}(P_1^1,S\circ P_2^3)$.

This is a property of the computed function, so it is extensional. It is non-trivial because some TMs compute this function and some compute different functions.

Explanation: The question depends only on the function computed by the machine, not on the machine itself. Therefore, Rice’s theorem (function version) applies, and thus it is undecidable.

One of two fixed functions

It is not decidable whether a given TM computes either of two fixed computable functions, for example $g$ or $f$.

Let $\mathcal{F}=\{\phi \mid \phi =g\vee \phi =f\}$. This property is extensional and non-trivial.

Explanation: The property depends only on the function computed by the machine. It is non-trivial because some TMs compute $g$ or $f$, and some compute other functions. Therefore, Rice’s theorem (function version) applies, and thus it is undecidable.

Primitive-recursive function

It is not decidable whether a given TM computes a primitive-recursive function.

Let $\mathcal{F}$ be the set of primitive-recursive functions. This property is extensional and non-trivial.

Explanation: The property depends only on the computed function. Some computable functions are primitive-recursive, and some are not, so the property is non-trivial. Therefore, Rice’s theorem (function version) applies, and thus it is undecidable.

Mu-recursive function

It is not decidable whether a given TM computes a function that can be built from base functions using ${\mu }_0$, $\mathbf{Pr}$, and composition.

Explanation: This property is trivial on Turing machines, because every Turing-computable function is already mu-recursive. Hence Rice’s theorem does not apply.

Tape change on empty input

It is not decidable whether a given TM changes its tape while running on the empty input.

Explanation: This depends on the internal behaviour of the machine, not only on the language or the computed function. It is not extensional, so Rice’s theorem does not apply.

More than 100 words

It is not decidable whether a given TM accepts more than $100$ words.

Let $\mathcal{E}=\{L\mid |L|>100\}$. This property is extensional and non-trivial.

Explanation: The property depends only on the accepted language. There are recursively enumerable languages with more than $100$ words and recursively enumerable languages with at most $100$ words, so Rice’s theorem applies, and thus it is undecidable.

Recursive language

It is not decidable whether a given TM accepts a recursive language.

Let $\mathcal{E}=\{L\mid L\text{ is recursive}\}$. This property is extensional and non-trivial.

Explanation: The property depends only on the accepted language. Some recursively enumerable languages are recursive, and some are not, so Rice’s theorem applies, and thus it is undecidable.