Rice's Theorem

Rice’s Theorem is another of the greatest results achieved in computability. It is one of the foundational theorems that make up computability. It states that all non-trivial semantic properties of programs are undecidable. This means that another program — namely, an algorithm — cannot decide for all the items in a set whether they hold a semantic property or not.

A brief discussion on semantic properties

Properties are basically divided in two fields:

• non-semantic properties (intensional properties);
• semantic properties (extensional properties).

The former are properties that do not concern semantics. You may think of “semantic properties” as regarding what a program does, while “non-semantic properties” are about syntactic properties — like the length of the program (in bytes, lines-of-code, etc.).

We denote such properties with $\Pi$. A property $\Pi$ is any subset of $\{ \varphi_{i} \}_{i \in \N}$.

Let $\Pi$ be a property. $\Pi$ is said to be semantic (extensional, or closed for extensional equality) if $\forall x, y \in \N : (x \in \Pi \text{ and } \varphi_{x} = \varphi_{y}) \implies y \in \Pi$. (Note that $\varphi_{x}$ denotes the execution of program $x$.)

Theorem

Let $\Pi$ be an extensional (semantic) property. $\Pi$ is recursive (thus fully decidable) if and only if it is trivial (a property $\Pi$ is said to be trivial if $\Pi = \emptyset \lor \Pi = \N$).

Proof

The theorem states “if and only if”, which is mathematically represented as $\iff$. To prove the theorem is thus necessary to prove both the conclusions from the two assumptions — as we do in Post’s Theorem. In other words, we have to prove: 1) $\Pi = \emptyset \lor \Pi = \N \implies \Pi \text{ recursive}$, and 2) $\Pi \text{ recursive} \implies \Pi = \emptyset \lor \Pi = \N$.

Let’s start with the first one, which is simpler.

1) $\Pi = \emptyset \lor \Pi = \N \implies \Pi \text{ recursive}$

There are two cases:

• $\Pi = \emptyset$. In this case, $\emptyset$ is recursive (for this set an even stronger property holds: it's regular!).
• $\Pi = \N$. In this case, again, $\N$ is recursive (it's even regular!).

The former implication has now been proven.

2) $\Pi \text{ recursive} \implies \Pi = \emptyset \lor \Pi = \N$

Let’s suppose that $\Pi$ is recursive. Then, it has a characteristic function $g$:

Of course, $g(x)$ is total recursive (so it halts on all inputs and is actually programmable for a Turing Machine).

Let’s assume, for contradiction, that $\Pi$ is non-trivial. Then there exist $a \in \Pi$ and $b \notin \Pi$ (since we assumed $\Pi$ is non-trivial, $\Pi \ne \N \land \Pi \ne \emptyset$; it follows that $\Pi$ contains some natural numbers, while some others are left out).

We can thus construct a function $h$:

Function $h$ is total recursive as well.

For the First Recursion Theorem by Kleene, it follows that $\exist n_0 : \varphi_{n_0} = \varphi_{h(n_0)}$.

Here there’s the contradiction:

• if $n_0 \in \Pi \implies h(n_0) \in \Pi$ because $\Pi$ is a semantic property (extensional). However, $h(n_0) = b \text{ and } b \notin \Pi$;
• if $n_0 \notin \Pi \implies h(n_0) \notin \Pi$. Nonetheless, $h(n_0) = a \text{ and } a \in \Pi$.

That is why $\Pi$ cannot be recursive and non-trivial. $\square$