Rice's Theorem
Rice’s theorem can be stated thus:
Every non-trivial semantic property of a program is undecidable.
Before we prove the theorem, let’s break down that statement:
“Semantic Property”
A ssemantic property is a property of the language, not the machine that is computing it. For example, this is a semantic property of a language:
- All strings in language $L$ are of the form $1^n0^n$.
This is not a semantic property:
- It takes my program $n$ steps to generate the first 100 strings in $L$.
Note the importance of differentiating between a semantic property and not:
- The halting problem is actually decidable for Linear Bouned Automata.
“Non-Trivial”
A trivial property is a property that either all languages have or no language has. A non-trivial property is everything else.
“Undecidable”
A program can either accept, reject, or run forever. If a program reaches an accept or reject state, we say it halts.
There are two types of programs: recognizers and deciders.
A recognizer is a program that can only tell you with certainty when it has succeeded to solve a problem (reached the accept state). It cannot always tell you when it has failed (if it goes into an infinite loop, there is no way to know if it’s in a loop, or if it’s just taking very long to solve the problem).
A decider is a program that always reaches either accepts or rejects. That is, you not only know when the problem was solved, but you also know when it was not solved.
A language is recognizable if there exists at least one program that can recognize it. For example, the following program reconizes $L = \{“342”\}$ (the language made up of only the string “342”):
- Read input.
- If input == “342” print “accept”.
- Else return to step 1.
This program recognizes $L$, but it does not decide $L$: if the input is in $L$, it accepts, but if it’s not, then it will run forever, and you will never know whether the input was not in $L$ or the program is just taking a long time.
A language is decidable if there exists a program that can decide it. All decidable languages are also recognizable. Here is a program that decides $L$:
- Read input.
- If input == “342” print “accept”.
- Else print “input rejected”.
The Halting Problem
Take the following language:
$HALT_{ TM } = \{ \langle M, w \rangle | M$ is a program and $M$ halts on input $w \}$
Remember, a program is itself just a string: any program can be written down as
a description, say an .rb file, and that file can be used as an input for
another program (or itself!). So $HALT_{ TM }$ is a language that consists of
all programs $M$ and inputs $w$ such that $M$ halts on $w$.
I won’t prove it in this post, but, as it turns out, $HALT_{ TM }$ is undecidable. Meaning it is not possible to write a program that decides whether an algorithm halts.
With this in mind, we can finally prove Rice’s theorem:
Rice’s Theorem
Recall the theorem:
Every non-trivial semantic property of a program is undecidable.
Yet another way of stating this is as follows:
The language $P_{ TM }$, described below, is undecidable: $P_{ TM } = \{ \langle M \rangle | M$ is a program and $L(M)$ has non-trivial property $P \}$. Where $L(M)$ means “The language of $M$”.
So, for example, it is not possible to write a program $R $ that takes as its input another program $M$ and decides whether the language of $M$ is regular (that is, if $M$ can be simplified and represented as a finite automation).
Proof
We can prove Rice’s theorem by contradiction. We will show that if $P_{ TM }$ is decidable then so is $HALT_{ TM }$. Since we know that $ HALT_{ TM }$ is undecidable, then $P_{ TM }$ must be undecidable too.
Assume that $P$ is some non-trivial semantic property and that it is possible to write a program $R$ that decides $P_{ TM }$. Here is how we could solve the halting problem with that program:
First, we write a program $T$ such that $\langle T \rangle $ is in $P_{ TM }$. Because $P$ is non-trivial, such a program must exist.
Take input $\langle M, w \rangle$ and use it to write a program $M_w$that takes $x$ as its input and does the following:
$M_w $:
- Run $M$ on input $w$. If $M$ halts, move on to step 2. 2. Run $T$ on $x$. Accept if $T$ accepts, and reject if $T$ rejects.
Here’s the clever part. We don’t actually have to run $M_w$:
All we need to know is that, if we were to run $M_w$, there are two possible outcomes:
- $M$ halts on input $w$, in which case $M_w$ reaches step 2.
- $M$ never halts and never reaches step 2.
But note that, if $M$ halts on $w$, then step 2 is simply to run $T$, which means that when $M$ halts on $w$, $ \langle M_w \rangle$is in $ P_{ TM }$.
So, if we were to run $R$ with input $\langle M_w \rangle$, it would be able to tell us whether it is in $P_{ TM }$, and that in turn would tell us if $M$ halts on $w$.
But this would mean that we could solve the halting problem, which we know is not possible.