If your integers have a bounded size, then your Turing machine is not Turing complete and can&#39;t run a Haskell interpreter.<br><br>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 computability.  But you will find that all the problems that are now theoretically solvable are still computationally intractable, and you are practically back where you started.<br>
<br>This doesn&#39;t mean that you can&#39;t make programs that can determine very interesting non-trivial properties of programs/functions, but it does mean that there is no way to make them always work.<br><br>- Job<br>
<br><br><div class="gmail_quote">On Tue, Jul 6, 2010 at 9:37 AM, Steffen Schuldenzucker <span dir="ltr">&lt;<a href="mailto:sschuldenzucker@uni-bonn.de">sschuldenzucker@uni-bonn.de</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">



  

<div bgcolor="#ffffff" text="#000000">
<br>
Forwarding this message to the list. <br>
<br>
No, I didn&#39;t think about the size of integers. For now, let all numbers
have some bounded size.<div class="im"><br>
<br>
-------- Original Message --------
<table border="0" cellpadding="0" cellspacing="0">
  <tbody>
    <tr>
      <th align="right" valign="baseline" nowrap>Subject: </th>
      <td>Re: [Haskell-cafe] Criteria for determining if a recursive
function can be implemented in constant memory</td>
    </tr>
    <tr>
      <th align="right" valign="baseline" nowrap>Date: </th>
      <td>Tue, 6 Jul 2010 13:25:57 +1200</td>
    </tr>
    <tr>
      <th align="right" valign="baseline" nowrap>From: </th>
      <td>Richard O&#39;Keefe <a href="mailto:ok@cs.otago.ac.nz" target="_blank">&lt;ok@cs.otago.ac.nz&gt;</a></td>
    </tr>
    <tr>
      <th align="right" valign="baseline" nowrap>To: </th>
      <td>Steffen Schuldenzucker <a href="mailto:sschuldenzucker@uni-bonn.de" target="_blank">&lt;sschuldenzucker@uni-bonn.de&gt;</a></td>
    </tr>
  </tbody>
</table>
<br>
<br>
</div><pre>On Jul 6, 2010, at 12:23 AM, Steffen Schuldenzucker wrote:
&gt; Given the definition of a recursive function f in, say, haskell,  
&gt; determine if f can be implemented in O(1) memory.

How are you supposed to handle integer arithmetic?

If you don&#39;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&#39;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>
</div>

<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br>