Tillmann Rendel wrote:
Hi Steffen,

Steffen Schuldenzucker wrote:
Given the definition of a recursive function f in, say, haskell, determine if f can be implemented in O(1) memory.

Constant functions are implementable in O(1) memory, but interpreters for turing-complete languages are not, so the property of being implementable in O(1) memory is non-trivial and therefore, by Rice's theorem, undecidable.

Damn Rice's theorum, spoiling everybody's fun all the time... ;-)

Of course, as I understand it, all the theorum says is that no single algorithm can give you a yes/no answer for *every* possible case. So the next question is "is it decidable in any 'interesting' cases?"

Then of course you have to go define 'interesting'...

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to