Forwarding this message to the list. No, I didn't think about the size of integers. For now, let all numbers have some bounded size. -------- Original Message -------- Subject: Re: [Haskell-cafe] Criteria for determining if a recursive function can be implemented in constant memory Date: Tue, 6 Jul 2010 13:25:57 +1200 From: Richard O'Keefe <ok@cs.otago.ac.nz> To: Steffen Schuldenzucker <sschuldenzucker@uni-bonn.de> 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.