[Haskell-cafe] Why is this strict in its arguments?

Tillmann Rendel rendel at rbg.informatik.tu-darmstadt.de
Wed Dec 5 06:48:09 EST 2007

Andrew Coppin wrote:
> *thinks*
> Conjecture #1: All nontrivial properties of a computer program are 
> undecidable in general.

That is the well-known Rice's theorem.

(A very handy one in exams about theoretical computer science, since you 
can smash so many questions with "follows from Rice").

> *thinks more*
> Conjecture #2: Conjecture #1 is undecidable...

But the question wether a nontrivial property of a computer program is 
decidable is *not* a property of computer programs itself. (it is a 
property of properties of computer programs instead). Rice's theorem 
doesn't apply to Rice's theorem.

(Thats the problem with smashing everything with Rice's theorem: it may 
be not applicable).


More information about the Haskell-Cafe mailing list