Re: [Haskell-cafe] Criteria for determining if a recursive function can be implemented in constant memory

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