46
$\begingroup$

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?

$\endgroup$
1
  • 10
    $\begingroup$ "According to Rice's theorem, everything is impossible." -- Nope. "Every property of a computer program is non-computable." -- Nope. You are not alone, though: most students encounter this misconception. $\endgroup$
    – Raphael
    Jul 18, 2012 at 10:21

2 Answers 2

41
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I can't get this answer.. (Sorry if I'm asking the same, but would be good to clarify this point). It says you can modify those programs by changing their syntax to get an extensional equivalent, but how to check those are extensional equivalent in the first place? You cannot use a program to compare if those programs functions in general have both that property, so when you say "modify it" I think it's possible because are simple examples, (would you add "modify it carefully"? or use a "good IDE for it"?..) I think once is modified you can't check in general so, perhaps Rice holds. $\endgroup$ Jun 16, 2014 at 18:22
  • 2
    $\begingroup$ In general you check that two particular programs are extensionally equal by proving that this is the case. Do you object to the fact that $n + m = m + n$ for all integers, even though a computer cannot "check" this equality for all values? Hopefully not. There is a difference between writing a program that computes a boolean value, and proving that a certain statement has a certain truth value. There are things we can prove but cannnot compute (such as the fact that two particular programs are extensionally equal, or that addition is commutative). $\endgroup$ Jun 17, 2014 at 7:48
  • 1
    $\begingroup$ Also, you are commiting a weird leap of reasoning in your reasoning: since extensional equality is not decidable, Rice's theorem might be false. How so? And just because extensional equality is undecidable, that does not mean there aren't any instances of it which we can decide. The ones I mentioned -- we can decide those. $\endgroup$ Jun 17, 2014 at 7:50
36
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I got lost after about the first sentence or so. Sorry. Can somebody elaborate on the difference between a semantic and a syntactic property? $\endgroup$ Jul 29, 2012 at 16:04
  • $\begingroup$ @MathematicalOrchid: You can safely ignore that sentence; the first paragraph holds all the information you need. I'll elaborate, anyway. $\endgroup$
    – Raphael
    Jul 29, 2012 at 21:03
  • 3
    $\begingroup$ Semantic = about what the program does. Syntactic = about what the program looks like. $\endgroup$ Dec 5, 2013 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.