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.