Re: How to use Rice Theorem to check if a function is undecidable or not?



Jym wrote:
I'd like to precise that Rice's theorem tells about *extensionnal* properties of programs.

Yes, that's an important point. The theorem is about properties of functions, not properties of indices, programs or lambda terms.

Of course, intensionnal properties are usually even harder to decide (not RE) so the precision is rather pointless...

This I don't understand. Many intensional properties, or properties of indices, programs or lambda terms, are decidable; being less than 10^1000, containing loops and being in normal form are all examples of decidable properties. Also, not all extensional properties are RE. Totality and constantness aren't, for example.

--
Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
.