Rice's theorem

Formal statement

Let ${\displaystyle \phi }$ be an admissible numbering of the partial computable functions, and let ${\displaystyle P}$ be a subset of ${\displaystyle \mathbb{N}}$. Suppose that:

1. ${\displaystyle P}$ is non-trivial: ${\displaystyle P}$ is neither empty nor ${\displaystyle \mathbb{N}}$ itself.
2. ${\displaystyle P}$ is extensional: for all integers ${\displaystyle m}$ and ${\displaystyle n}$, if ${\displaystyle {\phi }_m={\phi }_n}$, then ${\displaystyle m\in P⟺n\in P}$.

Then ${\displaystyle P}$ is undecidable.

A more concise statement can be made in terms of index sets: The only decidable index sets are ${\displaystyle \varnothing }$ and ${\displaystyle \mathbb{N}}$.

Examples

Given a program P that takes a natural number n and returns a natural number P(n), the following questions are undecidable:

• Does P terminate on a given n? (This is the halting problem.)
• Does P terminate on 0?
• Does P terminate on all n (i.e., is P total)?
• Does P terminate and return 0 on every input?
• Does P terminate and return 0 on some input?
• Does P terminate and return the same value for all inputs?
• Is P equivalent to a given program Q?

Proof by Kleene's recursion theorem

Assume for contradiction that ${\displaystyle P}$ is a non-trivial, extensional and computable set of natural numbers. Since ${\displaystyle P}$ is non-trivial, there is a natural number ${\displaystyle a\in P}$ and a natural number ${\displaystyle b\notin P}$. Define the total computable function ${\displaystyle Q}$ of ${\displaystyle e}$ and ${\displaystyle x}$ by ${\displaystyle Q_e(x)={\phi }_b(x)}$ when ${\displaystyle e\in P}$ and ${\displaystyle Q_e(x)={\phi }_a(x)}$ when ${\displaystyle e\notin P}$. By Kleene's recursion theorem, there exists ${\displaystyle e}$ such that ${\displaystyle {\phi }_e=Q_e}$. Then, if ${\displaystyle e\in P}$, we have ${\displaystyle {\phi }_e={\phi }_b}$, contradicting the extensionality of ${\displaystyle P}$ since ${\displaystyle b\notin P}$, and conversely, if ${\displaystyle e\notin P}$, we have ${\displaystyle {\phi }_e={\phi }_a}$, which again contradicts extensionality since ${\displaystyle a\in P}$.

Proof by reduction from the halting problem

Proof sketch

Suppose, for concreteness, that we have an algorithm for examining a program p and determining infallibly whether p is an implementation of the squaring function, which takes an integer d and returns d². The proof works just as well if we have an algorithm for deciding any other non-trivial property of program behavior (i.e. a semantic and non-trivial property), and is given in general below.

The claim is that we can convert our algorithm for identifying squaring programs into one that identifies functions that halt. We will describe an algorithm that takes inputs a and i and determines whether program a halts when given input i.

The algorithm for deciding this is conceptually simple: it constructs (the description of) a new program t taking an argument n, which (1) first executes program a on input i (both a and i being hard-coded into the definition of t), and (2) then returns the square of n. If a(i) runs forever, then t never gets to step (2), regardless of n. Then clearly, t is a function for computing squares if and only if step (1) terminates. Since we have assumed that we can infallibly identify programs for computing squares, we can determine whether t, which depends on a and i, is such a program; thus we have obtained a program that decides whether program a halts on input i. Note that our halting-decision algorithm never executes t, but only passes its description to the squaring-identification program, which by assumption always terminates; since the construction of the description of t can also be done in a way that always terminates, the halting-decision cannot fail to halt either.

halts (a,i) { define t(n) { a(i) <b id="mwnQ">return</b> n×n } <b id="mwng">return</b> is_a_squaring_function(t) }

This method does not depend specifically on being able to recognize functions that compute squares; as long as some program can do what we are trying to recognize, we can add a call to a to obtain our t. We could have had a method for recognizing programs for computing square roots, or programs for computing the monthly payroll, or programs that halt when given the input "Abraxas"; in each case, we would be able to solve the halting problem similarly.

Formal proof

For the formal proof, algorithms are presumed to define partial functions over strings and are themselves represented by strings. The partial function computed by the algorithm represented by a string a is denoted F_a. This proof proceeds by reductio ad absurdum: we assume that there is a non-trivial property that is decided by an algorithm, and then show that it follows that we can decide the halting problem, which is not possible, and therefore a contradiction.

Let us now assume that P(a) is an algorithm that decides some non-trivial property of F_a. Without loss of generality we may assume that P(no-halt) = "no", with no-halt being the representation of an algorithm that never halts. If this is not true, then this holds for the algorithm P that computes the negation of the property P. Now, since P decides a non-trivial property, it follows that there is a string b that represents an algorithm F_b and P(b) = "yes". We can then define an algorithm H(a, i) as follows:

1. construct a string t that represents an algorithm T(j) such that

• T first simulates the computation of F_a(i),
• then T simulates the computation of F_b(j) and returns its result.

2. return P(t).

We can now show that H decides the halting problem:

• Assume that the algorithm represented by a halts on input i. In this case F_t = F_b and, because P(b) = "yes" and the output of P(x) depends only on F_x, it follows that P(t) = "yes" and, therefore H(a, i) = "yes".
• Assume that the algorithm represented by a does not halt on input i. In this case F_t = F_no-halt, i.e., the partial function that is never defined. Since P(no-halt) = "no" and the output of P(x) depends only on F_x, it follows that P(t) = "no" and, therefore H(a, i) = "no".

Since the halting problem is known to be undecidable, this is a contradiction and the assumption that there is an algorithm P(a) that decides a non-trivial property for the function represented by a must be false.