On Jul 6, 2010, at 12:23 AM, Steffen Schuldenzucker wrote:
> Given the definition of a recursive function f in, say, haskell,  
> determine if f can be implemented in O(1) memory.

How are you supposed to handle integer arithmetic?

If you don't take the size of integers into account,
then since a Turing machine can do any computation,
it can run a Haskell interpreter, and since a Turing
machine's tape can be modelled by a single integer
(or more conveniently by two), any Haskell function
can be implemented in O(1) Integers.

If you do take the size of integers into account,
then
    pow2 n = loop n 1
      where loop 0 a = a
            loop (m+1) a = loop m (a+a)
requires O(n) memory.