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$:

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$:

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$