[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).
Tillmann
More information about the Haskell-Cafe
mailing list