<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
<br>
Forwarding this message to the list. <br>
<br>
No, I didn't think about the size of integers. For now, let all numbers
have some bounded size.<br>
<br>
-------- Original Message --------
<table class="moz-email-headers-table" border="0" cellpadding="0"
cellspacing="0">
<tbody>
<tr>
<th valign="BASELINE" align="RIGHT" nowrap="nowrap">Subject: </th>
<td>Re: [Haskell-cafe] Criteria for determining if a recursive
function can be implemented in constant memory</td>
</tr>
<tr>
<th valign="BASELINE" align="RIGHT" nowrap="nowrap">Date: </th>
<td>Tue, 6 Jul 2010 13:25:57 +1200</td>
</tr>
<tr>
<th valign="BASELINE" align="RIGHT" nowrap="nowrap">From: </th>
<td>Richard O'Keefe <a class="moz-txt-link-rfc2396E" href="mailto:ok@cs.otago.ac.nz"><ok@cs.otago.ac.nz></a></td>
</tr>
<tr>
<th valign="BASELINE" align="RIGHT" nowrap="nowrap">To: </th>
<td>Steffen Schuldenzucker <a class="moz-txt-link-rfc2396E" href="mailto:sschuldenzucker@uni-bonn.de"><sschuldenzucker@uni-bonn.de></a></td>
</tr>
</tbody>
</table>
<br>
<br>
<pre>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.</pre>
</body>
</html>