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

Tillmann Rendel rendel at Mathematik.Uni-Marburg.de
Mon Jul 5 09:05:08 EDT 2010

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.


More information about the Haskell-Cafe mailing list