# Rice's Theorem: Intro (Math 1)

Rice’s The­o­rem says that you can’t in gen­eral figure out any­thing about what a com­puter pro­gram out­puts just by look­ing at the pro­gram. Speci­fi­cally, we think of pro­grams as tak­ing in­puts, do­ing some kind of com­pu­ta­tion on the in­put, and pos­si­bly even­tu­ally stop­ping and giv­ing an out­put. Only “pos­si­bly” be­cause some­times pro­grams get in an in­finite loop and go for­ever. The as­sign­ment that takes an in­put to the out­put of a pro­gram on that in­put (if it ex­ists) is called the par­tial func­tion com­puted by that pro­gram note”Par­tial” func­tions be­cause the out­put doesn’t ex­ist if the pro­gram runs for­ever..

Rice’s The­o­rem says that for any prop­erty of par­tial func­tions, you can’t write a pro­gram that looks at some other pro­gram’s source code, and tells you whether that pro­gram com­putes a func­tion with the prop­erty noteThis is true ex­cept for “triv­ial” prop­er­ties like “all par­tial func­tions” or “no par­tial func­tions,” which are easy to write pro­grams to test..

For ex­am­ple, say we want to know whether a pro­gram com­putes the Fibonacci se­quence, i.e. re­turns the $$n$$th Fibonacci num­ber on in­put $$n$$. If we try to write a Fibonacci-checker pro­gram that tells us whether pro­grams com­pute the Fibonacci se­quence, we’re go­ing to have a hard time, be­cause by Rice’s The­o­rem it’s im­pos­si­ble!

There might be some pro­grams for which we can say “yes, this pro­gram definitely com­putes the Fibonacci se­quence,” but we can’t write a gen­eral pro­ce­dure that always tells whether some pro­gram com­putes the Fibonacci se­quence; there are some very con­voluted pro­grams that com­pute it, but not ob­vi­ously, and if you mod­ify the Fibonacci-checker to han­dle some of them, there will always be even more con­voluted pro­grams that it doesn’t work on.

We make a dis­tinc­tion be­tween pro­grams and (par­tial) func­tions com­puted by pro­grams. There are usu­ally many pro­grams that com­pute the same func­tion. Rice’s The­o­rem only cares about the par­tial func­tions; it’s pos­si­ble to test state­ments about pro­grams, like “has fewer than 100 lines.” But this kind of state­ment won’t always tell you some­thing about the func­tion the pro­gram com­putes.

# Proof

To prove Rice’s The­o­rem, we’ll use the halt­ing the­o­rem, which says that you can’t write a pro­gram that can always tell whether some pro­gram will halt on some in­put. Here’s how the proof will go: sup­pose you come up with a pro­gram that checks whether pro­grams com­pute par­tial func­tions with some prop­erty, e.g. you suc­cess­fully write a Fibonacci-checker. We’ll then use the Fibonacci-checker to de­sign a Halt-checker, which can tell when a pro­gram halts. But this is im­pos­si­ble by the Halt­ing the­o­rem, so this couldn’t be the case: your Fibonacci-checker must not work!

We need to make a cou­ple of as­sump­tions. First, that the empty func­tion, mean­ing the func­tion “com­puted” by a pro­gram that always en­ters an in­finite loop re­gard­less of its in­put, does not satisfy the prop­erty. If it does, we can re­place the prop­erty by its op­po­site (say, re­place “com­putes the Fibonacci se­quence” with “doesn’t com­pute the Fibonacci se­quence”). If we can tell whether a pro­gram com­putes a func­tion that doesn’t have the prop­erty, then we can tell when it does, sim­ply be re­vers­ing the out­put.

Se­cond, we as­sume there is some pro­gram that does com­pute a func­tion with the prop­erty, i.e. a pro­gram that the checker says “yes” to. If there isn’t, we could have the checker always say “no.” Say the pro­gram $$s$$ com­putes a func­tion with the prop­erty.

Now sup­pose you have a checker $$C$$ that, when given a pro­gram as in­put, re­turns whether the pro­gram com­putes a func­tion with some prop­erty of in­ter­est. We want to test whether some pro­gram $$M$$ halts, when given in­put $$x$$.

We start by build­ing a new pro­gram, called $$Proxy_s$$, which does the fol­low­ing on some in­put $$z$$:

• Run $$M$$ on in­put $$x$$.

• Run $$s$$ on in­put $$z$$, and re­turn the re­sult.

If $$M$$ halts on $$x$$, $$Proxy_s$$ moves on to the sec­ond step, and re­turns the same value as $$s$$. Since they re­turn the same value (or no value, be­cause of an in­finite loop) on ev­ery pos­si­ble in­put, $$s$$ and $$Proxy_s$$ com­pute the same func­tion. So $$Proxy_s$$ com­putes a func­tion with the prop­erty.

If $$M$$ doesn’t halt on $$x$$, $$Proxy_s$$ never finishes the first step, and runs for­ever. So $$Proxy_s$$ always ends up in an in­finite loop, which means it com­putes the empty func­tion. So $$Proxy_s$$ com­putes a func­tion that doesn’t have the prop­erty.

What hap­pens if we plug $$Proxy_s$$ as in­put into $$C$$? If $$C$$ says “yes,” $$Proxy_s$$ com­putes a func­tion with the prop­erty, which means $$M$$ halts on $$x$$. If $$C$$ says “no,” $$Proxy_s$$ doesn’t com­pute a func­tion with the prop­erty, so $$M$$ doesn’t halt on $$x$$.

So we can tell whether $$M$$ halts on $$x$$! All we have to do is write this proxy func­tion, and ask $$C$$ whether its func­tion has the prop­erty. But the Halt­ing the­o­rem says we can’t do this! That means $$C$$ can’t ex­ist, and we can’t write a checker to see whether pro­grams com­pute func­tions with the prop­erty.

As an ex­am­ple, sup­pose we have a Fibonacci-checker $$fib\_checker$$. The fol­low­ing Python pro­gram com­putes the Fibonacci num­bers, and so $$fib\_checker$$ says “yes” to it:

def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a+b
re­turn a


Then, for some pro­gram $$M$$ and in­put $$x$$, $$Proxy_{fib}$$ is the pro­gram:

def Proxy_fib(z):
M(x)
re­turn fib(z)


If $$fib\_checker$$ works, this pro­gram says whether $$M$$ halts on $$x$$:

def halts(M,x)
re­turn fib_checker(Proxy_fib)


Ex­pand­ing this, we have the pro­gram:

def halts(M,x)
re­turn fib_checker(‴
M(x)
a, b = 0, 1
for i in range(n):
a, b = b, a+b
re­turn a
‴)


If $$M$$ halts on $$x$$, the pro­gram in­side the triple quotes com­putes the Fibonacci se­quence, so $$fib\_checker$$ re­turns $$true$$, and so does $$halts$$. If $$M$$ doesn’t halt on $$x$$, the pro­gram in the triple quotes also doesn’t halt, and re­turns the empty func­tion, which isn’t the Fibonacci se­quence. So $$fib\_checker$$ re­turns $$false$$, and so does $$halts$$.

Parents:

• Rice's Theorem

Rice’s The­o­rem tells us that if we want to de­ter­mine pretty much any­thing about the be­havi­our of an ar­bi­trary com­puter pro­gram, we can’t in gen­eral do bet­ter than just run­ning it.

• 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.