5 Dec
2007
5 Dec
'07
6:48 a.m.
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