# Rice's Theorem

Rice’s The­o­rem is a rather sur­pris­ing and very strong re­stric­tion on what we can de­ter­mine about the func­tion com­puted by an ar­bi­trary Tur­ing ma­chine. It tells us that for ev­ery non­triv­ial prop­erty of com­putable func­tions noteBy “non­triv­ial”, we mean there is at least one func­tion with that prop­erty and at least one with­out that prop­erty., there is no gen­eral pro­ce­dure which takes as its in­put a Tur­ing ma­chine, and com­putes whether or not the func­tion com­puted by that ma­chine has that prop­erty.

There­fore, if we want to dis­cover any­thing about the out­put of a gen­eral com­puter pro­gram, in gen­eral the best we can do is sim­ply run the pro­gram. As a corol­lary, there can be no fully gen­eral pro­ce­dure that checks whether a piece of com­puter code is free of bugs or not.

# For­mal statement

We will use the no­ta­tion $$[n]$$ for the $$n$$th Tur­ing ma­chine un­der some fixed num­ber­ing sys­tem. Each such ma­chine in­duces a par­tial func­tion, which we will also write as $$[n]$$ where this is un­am­bigu­ous due to con­text; then it makes sense to write $$[n](m)$$ for the value that ma­chine $$[n]$$ out­puts when it is run on in­put $$m$$.

Let $$A$$ be a non-empty, proper noteThat is, it is not the en­tire set. sub­set of $$\{ \mathrm{Graph}(n) : n \in \mathbb{N} \}$$, where $$\mathrm{Graph}(n)$$ is the graph of the par­tial func­tion com­puted by $$[n]$$, the $$n$$th Tur­ing ma­chine. Then there is no Tur­ing ma­chine $$[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 re­sult tells us, for ex­am­ple, that “no pro­ce­dure will ever be able to de­ter­mine whether an ar­bi­trary pro­gram is bug-free”, in prac­tice it may be pos­si­ble to de­ter­mine whether a large class of pro­grams is bug-free, while ac­cept­ing the fact that our pro­ce­dure might not be able to solve the fully gen­eral case.

• Ad­di­tion­ally, this re­sult only tells us about the graphs of the func­tions in ques­tion. We can de­ter­mine cer­tain prop­er­ties which are spe­cific to the Tur­ing ma­chine: for ex­am­ple, we can tell whether the pro­gram will halt in five steps, by sim­ply run­ning it for five steps. This does not con­tra­dict Rice, be­cause Rice tells us only about the ul­ti­mate an­swer the ma­chines spit out, and noth­ing about the pro­ce­dures they use to get to the an­swer; “the ma­chine halts in five steps” is not a prop­erty of the graph of the func­tion, but is a prop­erty of the Tur­ing ma­chine it­self.

• Rice’s the­o­rem is only a re­stric­tion on whether we can de­cide the sta­tus of a func­tion: that is, whether we can de­cide whether or not the func­tion com­puted by some ma­chine has a cer­tain prop­erty. Rice tells us noth­ing if we’re only look­ing for a pro­ce­dure that “must find out in finite time whether a func­tion does have a prop­erty, but is al­lowed to never give an an­swer if the func­tion doesn’t have the prop­erty”. For ex­am­ple, we can de­ter­mine whether a par­tial func­tion is defined any­where (that is, it is not the empty func­tion: the one which never out­puts any­thing, what­ever its in­put) by just at­tempt­ing to eval­u­ate the func­tion in par­allel at $$0$$, at $$1$$, at $$2$$, and so on. If the par­tial func­tion is defined any­where, then even­tu­ally one of the par­allel threads will dis­cover this fact; but if it is defined nowhere, then the pro­ce­dure might just spin on and on for­ever with­out giv­ing any out­put. How­ever, Rice’s the­o­rem does guaran­tee that there is no pro­ce­dure which will tell us in finite time whether or not its in­put is a func­tion which is defined some­where; even though we have just speci­fied a pro­ce­dure which will tell us in finite time if its in­put is defined some­where.

# Proof outline

Sev­eral proofs ex­ist: for ex­am­ple, one by re­duc­tion to the halt­ing prob­lem, and one stan­dalone proof. Here, we sketch the stan­dalone proof in broad strokes, be­cause it goes via a neat lemma.

The in­ter­me­di­ate lemma we prove is:

Let $$h: \mathbb{N} \to \mathbb{N}$$ be to­tal com­putable: that is, it halts on ev­ery in­put. Then there is $$n \in \mathbb{N}$$ such that $$\mathrm{Graph}(n) = \mathrm{Graph}(h(n))$$. noteAnd, more­over, we can ac­tu­ally find such an $$n$$.

That is, the “un­der­ly­ing func­tion” of $$n$$ - the par­tial func­tion com­puted by $$[n]$$ - has the same out­put, at ev­ery point, as the func­tion com­puted by $$[h(n)]$$. If we view $$h$$ as a way of ma­nipu­lat­ing a pro­gram (as speci­fied by its de­scrip­tion num­ber), then this fixed-point the­o­rem states that we can find a pro­gram whose un­der­ly­ing func­tion is not changed at all by $$h$$.

This lemma might be some­what sur­pris­ing: it “ought” to be pos­si­ble to find a change one could make to ar­bi­trary com­puter code, with the guaran­tee that the al­tered code must do some­thing differ­ent to the origi­nal. The fixed-point the­o­rem tells us that this is not the case.

The proof of the lemma is very difficult to un­der­stand fully, but rather easy to state, be­cause there are sev­eral use­ful short­hands which hide much of the com­plex­ity of what is re­ally go­ing on; full de­tails, along with a worked ex­am­ple, can be found in the ac­com­pa­ny­ing lens.

Once we have the in­ter­me­di­ate lemma, Rice’s the­o­rem it­self fol­lows quickly. In­deed, if the op­er­a­tion of “de­ter­mine whether a ma­chine com­putes a func­tion whose graph is in $$A$$ or not” is com­putable, then we can do the fol­low­ing pro­ce­dure:

• Take some com­puter code as in­put.

• Deter­mine whether the code speci­fies a func­tion whose graph is in $$A$$ or not.

• If it is in $$A$$, out­put code for a spe­cific (prob­a­bly un­re­lated) func­tion whose graph is not in $$A$$.

• Other­wise, out­put code for a spe­cific (prob­a­bly un­re­lated) func­tion whose graph is in $$A$$.

The fixed-point the­o­rem tells us that some pro­gram isn’t changed by the above pro­ce­dure; but the pro­ce­dure is guaran­teed to in­ter­change pro­grams-from-$A$ with pro­grams-not-from-$A$, so the pro­ce­dure can’t have any fixed points af­ter all.

Children:

Parents:

• Turing machine

A Tur­ing Ma­chine is a sim­ple math­e­mat­i­cal model of com­pu­ta­tion that is pow­er­ful enough to de­scribe any com­pu­ta­tion a com­puter can do.

• Is the differ­ence be­tween “whether or not” and “if” triv­ial in en­glish (I’m French) ? I think I un­der­stand the third point in the Caveats sec­tion. How­ever I only un­der­stand the last sen­tence from con­text. Is there already an ex­pla­na­tion on Ar­bital of the differ­ence be­tween “whether or not” and “if” as used here ?

• This is not uni­ver­sally agreed-upon, but I use “$A$ de­cides whether or not $$B$$ holds” to mean “$A$ out­puts $$1$$ if $$B$$ holds, and out­puts $$0$$ oth­er­wise”.

If I said “$A$ de­cides if $$B$$ holds”, I would con­sider that am­bigu­ous: it might mean “$A$ out­puts $$1$$ if $$B$$ holds” with­out the re­quire­ment on $$A$$’s be­havi­our if $$B$$ doesn’t hold.