Rice's Theorem

Published May 19, 2022  -  By Marco Garosi

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 {φi}iN\{ \varphi_{i} \}_{i \in \N}.

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


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 Π=Π=N\Pi = \emptyset \lor \Pi = \N).


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) Π=Π=N    Π recursive\Pi = \emptyset \lor \Pi = \N \implies \Pi \text{ recursive}, and 2) Π recursive    Π=Π=N\Pi \text{ recursive} \implies \Pi = \emptyset \lor \Pi = \N.

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

1) Π=Π=N    Π recursive\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!).
  • Π=N\Pi = \N. In this case, again, N\N is recursive (it's even regular!).

The former implication has now been proven.

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

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

g(x)={1if xΠ0if xΠ g(x) = \begin{cases} 1 &\text{if } x \in \Pi \\ 0 &\text{if } x \notin \Pi \end{cases}

Of course, g(x)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Πa \in \Pi and bΠb \notin \Pi (since we assumed Π\Pi is non-trivial, ΠNΠ\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 hh:

h(x)={bif g(x)=1    xΠaif g(x)=0    xΠ h(x) = \begin{cases} b &\text{if } g(x) = 1 \iff x \in \Pi \\ a &\text{if } g(x) = 0 \iff x \notin \Pi \end{cases}

Function hh is total recursive as well.

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

Here there’s the contradiction:

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

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

Share on: