>
> On Jul 6, 2010, at 6:37, Steffen Schuldenzucker
> mailto:sschuldenzuc...@uni-bonn.de>> wrote:
>
>>
>> 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.
>>
On 7/5/2010 8:33 PM, Andrew Coppin wrote:
Tillmann Rendel wrote:
Hi Steffen,
Steffen Schuldenzucker wrote:
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 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
>
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
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 T
Tillmann Rendel wrote:
Hi Steffen,
Steffen Schuldenzucker wrote:
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
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 functi
Dear Cafe,
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.
First I thought the solution would be "check