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