Hum. You are right and I'm probably asking the wrong questions.
My original question was when it was possible to eliminate stack frames. For
example, in the 'f' function from my first post, we know that none of the
variables x and y will be needed after the recursive call to f, so we can just
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
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:
If your integers have a bounded size, then your Turing machine is not Turing
complete and can't run a Haskell interpreter.
You might be tempted to just make the numbers really big, but bounded, and
then say that you can still run most interesting programs while skirting the
issue of non
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
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
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
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
