Hi Steffen,
Steffen Schuldenzucker wrote:
since a little discussion with my tutor I am wondering how the following
problem can be solved and if it is decidable:
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.
Tillmann
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
