Rice’s Theorem is a rather surprising and very strong restriction on what we can determine about the function computed by an arbitrary Turing machine. It tells us that for every nontrivial property of computable functions noteBy “nontrivial”, we mean there is at least one function with that property and at least one without that property., there is no general procedure which takes as its input a Turing machine, and computes whether or not the function computed by that machine has that property.

Therefore, if we want to discover anything about the output of a general computer program, in general the best we can do is simply run the program. As a corollary, there can be no fully general procedure that checks whether a piece of computer code is free of bugs or not.

Formal statement

We will use the notation \([n]\) for the \(n\)th Turing machine under some fixed numbering system. Each such machine induces a partial function, which we will also write as \([n]\) where this is unambiguous due to context; then it makes sense to write \([n](m)\) for the value that machine \([n]\) outputs when it is run on input \(m\).

Let \(A\) be a non-empty, proper noteThat is, it is not the entire set. subset of \(\{ \mathrm{Graph}(n) : n \in \mathbb{N} \}\), where \(\mathrm{Graph}(n)\) is the graph of the partial function computed by \([n]\), the \(n\)th Turing machine. Then there is no Turing machine \([r]\) such that:

• \([r](i)\) is \(1\) if \(\mathrm{Graph}(i) \in A\)

• \([r](i)\) is \(0\) if \(\mathrm{Graph}(i) \not \in A\).

Caveats

• While this result tells us, for example, that “no procedure will ever be able to determine whether an arbitrary program is bug-free”, in practice it may be possible to determine whether a large class of programs is bug-free, while accepting the fact that our procedure might not be able to solve the fully general case.

• Additionally, this result only tells us about the graphs of the functions in question. We can determine certain properties which are specific to the Turing machine: for example, we can tell whether the program will halt in five steps, by simply running it for five steps. This does not contradict Rice, because Rice tells us only about the ultimate answer the machines spit out, and nothing about the procedures they use to get to the answer; “the machine halts in five steps” is not a property of the graph of the function, but is a property of the Turing machine itself.

• Rice’s theorem is only a restriction on whether we can decide the status of a function: that is, whether we can decide whether or not the function computed by some machine has a certain property. Rice tells us nothing if we’re only looking for a procedure that “must find out in finite time whether a function does have a property, but is allowed to never give an answer if the function doesn’t have the property”. For example, we can determine whether a partial function is defined anywhere (that is, it is not the empty function: the one which never outputs anything, whatever its input) by just attempting to evaluate the function in parallel at \(0\), at \(1\), at \(2\), and so on. If the partial function is defined anywhere, then eventually one of the parallel threads will discover this fact; but if it is defined nowhere, then the procedure might just spin on and on forever without giving any output. However, Rice’s theorem does guarantee that there is no procedure which will tell us in finite time whether or not its input is a function which is defined somewhere; even though we have just specified a procedure which will tell us in finite time if its input is defined somewhere.

Proof outline

Several proofs exist: for example, one by reduction to the halting problem, and one standalone proof. Here, we sketch the standalone proof in broad strokes, because it goes via a neat lemma.

The intermediate lemma we prove is:

Let \(h: \mathbb{N} \to \mathbb{N}\) be total computable: that is, it halts on every input. Then there is \(n \in \mathbb{N}\) such that \(\mathrm{Graph}(n) = \mathrm{Graph}(h(n))\). noteAnd, moreover, we can actually find such an \(n\).

That is, the “underlying function” of \(n\) - the partial function computed by \([n]\) - has the same output, at every point, as the function computed by \([h(n)]\). If we view \(h\) as a way of manipulating a program (as specified by its description number), then this fixed-point theorem states that we can find a program whose underlying function is not changed at all by \(h\).

This lemma might be somewhat surprising: it “ought” to be possible to find a change one could make to arbitrary computer code, with the guarantee that the altered code must do something different to the original. The fixed-point theorem tells us that this is not the case.

The proof of the lemma is very difficult to understand fully, but rather easy to state, because there are several useful shorthands which hide much of the complexity of what is really going on; full details, along with a worked example, can be found in the accompanying lens.

Once we have the intermediate lemma, Rice’s theorem itself follows quickly. Indeed, if the operation of “determine whether a machine computes a function whose graph is in \(A\) or not” is computable, then we can do the following procedure:

• Take some computer code as input.

• Determine whether the code specifies a function whose graph is in \(A\) or not.

• If it is in \(A\), output code for a specific (probably unrelated) function whose graph is not in \(A\).

• Otherwise, output code for a specific (probably unrelated) function whose graph is in \(A\).

The fixed-point theorem tells us that some program isn’t changed by the above procedure; but the procedure is guaranteed to interchange programs-from-$A$ with programs-not-from-$A$, so the procedure can’t have any fixed points after all.