From: Daniel Radetsky (daniel@radray.us)
Date: Sat Aug 28 2004 - 15:09:16 MDT
On Sat, 28 Aug 2004 08:35:08 +0200
Tomaz Kristan <tomaz.kristan@gmail.com> wrote:
> On Sat, 28 Aug 2004 01:26:53 -0700, Daniel Radetsky <daniel@radray.us> wrote:
>
> > I don't think running out
> > of memory can be considered a halt. A computable function is one that *could* be
> > computed by a Turing Machine, and Turing machines don't run out of memory.
> >
>
> There is no ideal Turing machine. The question of what an ideal TM
> might, or might not do, is out of this world. A closely related
> question with that one in the thread about the infinity, kindly closed
> by Eliezer.
If you prefer to talk about it in practical terms, we can just say we'll keep
adding more memory as the computer's use of it increases. We don't have to
actually give it infinite memory, just more than it needs at any given time. In
this case, we're talking about getting all the possible partitions of a number
into two numbers (I believe this is the correct terminology; someone please
correct me if I'm wrong), and then checking the two numbers for primality. This
is probably a "bad" algorithm, and so we could probably add storage space far
faster than it would use it up. For practical purposes, this is infinite memory.
Daniel Radetsky
This archive was generated by hypermail 2.1.5 : Tue Feb 21 2006 - 04:22:43 MST