Perplexed by Rice's theorem

Question

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time!

---

Of course, Rice's theorem doesn't simply say "everything is impossible". It says something rather more specific: "Every property of a computer program is non-computable."

(If you want to split hairs, every "non-trivial" property. That is, properties which all programs posses or no programs posses are trivially computable. But any other property is non-computable.)

That's what the theorem says, or appears to say. And presumably a great number of very smart people have carefully verified the correctness of this theorem. But it seems to completely defy logic! There are numerous properties of programs which are trivial to compute!! For example:

• How many steps does a program execute before halting? To decide whether this number is finite or infinite is precisely the Halting Problem, which is non-computable. To decide whether this number is greater or less than some finite $n$ is trivial! Just run the program for up to $n$ steps and see if it halts or not. Easy!

• Similarly, does the program use more or less than $n$ units of memory in its first $m$ execution steps? Trivially computable.

• Does the program text mention a variable named $k$? A trivial textual analysis will reveal the answer.

• Does the program invoke command $\sigma$? Again, scan the program text looking for that command name.

I can see plenty of properties that do look non-computable as well; e.g., how many additions does a complete run of the program perform? Well, that's nearly the same as asking how many steps the program performs, which is virtually the Halting Problem. But it looks like there are boat-loads of program properties which a really, really easy to compute. And yet, Rice's theorem insists that none of them are computable.

What am I missing here?

Answer 1

For the purposes of this discussion, a "program" is a piece of code which always takes an integer as an input, and either runs forever or returns an integer. We say that two programs $f$ and $g$ are extensionally equal if they compute the same function, i.e., for every number $n$ either both $f(n)$ and $g(n)$ run forever, or they both terminate and output the same number.

An extensional property of programs is a property $P$ that respects extensional equality, i.e., if $f$ and $g$ are extensionally equal then they either both have the property $P$ or both do not have it.

Here are some examples of non-extensional properties:

1. The program halts within $n$ steps. (We can always modify a program to an extensionally equal one that runs longer.)
2. The program uses fewer than $n$ memory cells within the first $m$ steps of execution. (We can always modify a program to an extensionally equal one so that it uses up some memory for no good reason.)
3. The program text mentions a variable named k. (We can rename variables.)
4. Does the program invoke command $\sigma$. This may depend a bit on what $\sigma$ is, but if it is something that can be simulated in some way, then we can evade $\sigma$ and still have a program which is extensionally equal to the original one.

I am sure you have noticed that I listed precisely your alleged counter-examples to Rice's theorem, which says:

Theorem (Rice): A computable extensional property of programs either holds of all programs or of none.

There is another way to explain this: you have to distinguish between a program and the function it computes. Many different programs compute the same function (they are all extensionally equal). Rice's theorem is about properties of functions, not about properties of programs that compute them.

Answer 2

Fundamental misunderstanding:

Every property of a computer program is non-computable

That is not what Rice's theorem talks about. It talks about properties of functions and that the set of programs computing this function is not decidable. Formally, given $\emptyset \subset P \subset \mathsf{RE}$ the set

$\qquad \displaystyle \{ \langle M \rangle \mid f_M \in P \}$

is not decidable. For the properties you mention, you won't find a suitable $P$ for which the set of programs has this form. Some programs for one function may have the property while others (for the same function) may not. See here for some examples.

Rice's theorem deals with semantic properties (properties of the function computed by a program, e.g. domain or value range). What you refer to are syntactic properties (properties of the program, such as runtime or how many variables are used).

Not much seems to be known for syntactic properties; see this question.