Rice's Theorem

https://arbital.com/p/rice_theorem

by Patrick Stevens Jul 28 2016 updated Aug 14 2016

Rice's Theorem tells us that if we want to determine pretty much anything about the behaviour of an arbitrary computer program, we can't in general do better than just running it.


[summary: Rice's Theorem tells us that for every nontrivial property of computable functions, 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. That is, there is no general way to determine anything nontrivial about the output of an arbitrary Turing machine.]

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 %%note:By "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 [description_number 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 %%note:That is, it is not the entire set.%% subset of $~$\{ \mathrm{Graph}(n) : n \in \mathbb{N} \}$~$, where $~$\mathrm{Graph}(n)$~$ is the [graph_of_a_function graph] of the Partial function computed by $~$[n]$~$, the $~$n$~$th Turing machine. Then there is no Turing machine $~$[r]$~$ such that:

Caveats

Proof outline

Several proofs exist: for example, one by reduction to the [halting_problem 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_function 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))$~$. %%note:And, 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:

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.


Comments

Sylvain Chevalier

Is the difference between "whether or not" and "if" trivial in english (I'm French) ? I think I understand the third point in the Caveats section. However I only understand the last sentence from context. Is there already an explanation on Arbital of the difference between "whether or not" and "if" as used here ?

Patrick Stevens

This is not universally agreed-upon, but I use "$~$A$~$ decides whether or not $~$B$~$ holds" to mean "$~$A$~$ outputs $~$1$~$ if $~$B$~$ holds, and outputs $~$0$~$ otherwise".

If I said "$~$A$~$ decides if $~$B$~$ holds", I would consider that ambiguous: it might mean "$~$A$~$ outputs $~$1$~$ if $~$B$~$ holds" without the requirement on $~$A$~$'s behaviour if $~$B$~$ doesn't hold.