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.

Rice's Theorem (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.

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.