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.