Rice’s Theorem

WikiLast edit: Aug 14, 2016, 5:28 PM by Patrick Stevens

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 [1], 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 for the th Turing machine under some fixed numbering system. Each such machine induces a partial function, which we will also write as where this is unambiguous due to context; then it makes sense to write for the value that machine outputs when it is run on input .

Let be a non-empty, proper [2] subset of , where is the graph of the partial function computed by , the th Turing machine. Then there is no Turing machine such that:

Caveats

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 be total computable: that is, it halts on every input. Then there is such that . [3]

That is, the “underlying function” of - the partial function computed by - has the same output, at every point, as the function computed by . If we view 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 .

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 or not” is computable, then we can do the following procedure:

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- with programs-not-from-, so the procedure can’t have any fixed points after all.

  1. ^︎

    By “nontrivial”, we mean there is at least one function with that property and at least one without that property.

  2. ^︎

    That is, it is not the entire set.

  3. ^︎

    And, moreover, we can actually find such an .