Rice’s Theorem says that you can’t in general figure out anything about what a computer program outputs just by looking at the program. Specifically, we think of programs as taking inputs, doing some kind of computation on the input, and possibly eventually stopping and giving an output. Only “possibly” because sometimes programs get in an infinite loop and go forever. The assignment that takes an input to the output of a program on that input (if it exists) is called the partial function computed by that program note”Partial” functions because the output doesn’t exist if the program runs forever..

Rice’s Theorem says that for any property of partial functions, you can’t write a program that looks at some other program’s source code, and tells you whether that program computes a function with the property noteThis is true except for “trivial” properties like “all partial functions” or “no partial functions,” which are easy to write programs to test..

For example, say we want to know whether a program computes the Fibonacci sequence, i.e. returns the \(n\)th Fibonacci number on input \(n\). If we try to write a Fibonacci-checker program that tells us whether programs compute the Fibonacci sequence, we’re going to have a hard time, because by Rice’s Theorem it’s impossible!

There might be some programs for which we can say “yes, this program definitely computes the Fibonacci sequence,” but we can’t write a general procedure that always tells whether some program computes the Fibonacci sequence; there are some very convoluted programs that compute it, but not obviously, and if you modify the Fibonacci-checker to handle some of them, there will always be even more convoluted programs that it doesn’t work on.

We make a distinction between programs and (partial) functions computed by programs. There are usually many programs that compute the same function. Rice’s Theorem only cares about the partial functions; it’s possible to test statements about programs, like “has fewer than 100 lines.” But this kind of statement won’t always tell you something about the function the program computes.

Proof

To prove Rice’s Theorem, we’ll use the halting theorem, which says that you can’t write a program that can always tell whether some program will halt on some input. Here’s how the proof will go: suppose you come up with a program that checks whether programs compute partial functions with some property, e.g. you successfully write a Fibonacci-checker. We’ll then use the Fibonacci-checker to design a Halt-checker, which can tell when a program halts. But this is impossible by the Halting theorem, so this couldn’t be the case: your Fibonacci-checker must not work!

We need to make a couple of assumptions. First, that the empty function, meaning the function “computed” by a program that always enters an infinite loop regardless of its input, does not satisfy the property. If it does, we can replace the property by its opposite (say, replace “computes the Fibonacci sequence” with “doesn’t compute the Fibonacci sequence”). If we can tell whether a program computes a function that doesn’t have the property, then we can tell when it does, simply be reversing the output.

Second, we assume there is some program that does compute a function with the property, i.e. a program that the checker says “yes” to. If there isn’t, we could have the checker always say “no.” Say the program \(s\) computes a function with the property.

Now suppose you have a checker \(C\) that, when given a program as input, returns whether the program computes a function with some property of interest. We want to test whether some program \(M\) halts, when given input \(x\).

We start by building a new program, called \(Proxy_s\), which does the following on some input \(z\):

• Run \(M\) on input \(x\).

• Run \(s\) on input \(z\), and return the result.

If \(M\) halts on \(x\), \(Proxy_s\) moves on to the second step, and returns the same value as \(s\). Since they return the same value (or no value, because of an infinite loop) on every possible input, \(s\) and \(Proxy_s\) compute the same function. So \(Proxy_s\) computes a function with the property.

If \(M\) doesn’t halt on \(x\), \(Proxy_s\) never finishes the first step, and runs forever. So \(Proxy_s\) always ends up in an infinite loop, which means it computes the empty function. So \(Proxy_s\) computes a function that doesn’t have the property.

What happens if we plug \(Proxy_s\) as input into \(C\)? If \(C\) says “yes,” \(Proxy_s\) computes a function with the property, which means \(M\) halts on \(x\). If \(C\) says “no,” \(Proxy_s\) doesn’t compute a function with the property, 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 function, and ask \(C\) whether its function has the property. But the Halting theorem says we can’t do this! That means \(C\) can’t exist, and we can’t write a checker to see whether programs compute functions with the property.

As an example, suppose we have a Fibonacci-checker \(fib\_checker\). The following Python program computes the Fibonacci numbers, 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
    return a

Then, for some program \(M\) and input \(x\), \(Proxy_{fib}\) is the program:

def Proxy_fib(z):
    M(x)
    return fib(z)

If \(fib\_checker\) works, this program says whether \(M\) halts on \(x\):

def halts(M,x)
    return fib_checker(Proxy_fib)

Expanding this, we have the program:

def halts(M,x)
    return fib_checker('''
                        M(x)
                        a, b = 0, 1
                        for i in range(n):
                            a, b = b, a+b
                        return a
                      ''')

If \(M\) halts on \(x\), the program inside the triple quotes computes the Fibonacci sequence, so \(fib\_checker\) returns \(true\), and so does \(halts\). If \(M\) doesn’t halt on \(x\), the program in the triple quotes also doesn’t halt, and returns the empty function, which isn’t the Fibonacci sequence. So \(fib\_checker\) returns \(false\), and so does \(halts\).