Infinity and you (was Re: Turing Compliant?)

[William Tanksley]

On Tue, 07 Sep 1999 00:52:18 GMT, Graham Hughes wrote:
>>>>>> "William" == William Tanksley <wtanksle at dolphin.openprojects.net> writes:

><off-topic pedantry>

More and more!  :-)

>    William> On 6 Sep 1999 23:22:23 GMT, Aahz Maruch wrote:

[for some history: someone claimed that Turing machines required an
infinite amount of memory.  Someone else contradicted that, claiming that
they only needed an "unbounded" amount.  I argued that there was no
distinction.]

>    >> Consider the real numbers in the range 0.0 through 1.0.  They are
>    >> bounded but infinite.

>    William> ...but he's speaking of memory, an item which has to be
>    William> enumerated in order to be measured.  Thus, unbounded memory
>    William> is infinite memory.

>I don't understand `enumerated in order to be measured'.  Memory can be
>trivially mapped onto the integers, and a bounded amount of memory has a
>one-to-one mapping onto a bounded set of integers.

Are you arguing that "enumeration" isn't mapping some set onto the
integers?  (As opposed to remuneration<->renumeration, a mispelling I
applied once and only once, to the accompaniment of great heckling. :-)

The inevitable conclusion is that an unbounded amount of memory has a
one-to-one mapping onto an unbounded set of integers (your words).  The
resultant set of integers is 'infinite' as well as unbounded, so the
amount of memory is also infinite.

>What `not infinite, unbounded' means is that any given Turing machine
>can use at most a finite amount of memory in a finite time, but that
>there is no upper limit to the amount of memory that any given Turing
>machine may use.  You may in practice need an infinite amount of memory
>to simulate any and all Turing machines; but you'll need an infinite
>amount of time for them to use all that memory, too, so nobody much
>cares.

Ah.  So your point is that we can always stop the computation and buy more
memory, right?

Not a bad point.  I wouldn't call it practical, but it's more practical
than infinite amounts of memory -- or Turing machines in general (admit
it, TMs are silly).

>An important distinction, however, and the reason we can speak of
>putting Turing machines in a computer at all, is that the memory to run
>any one particular Turing machine may well be bounded, and thus
>representable in a real world computer.

This distinction matters only if we can refuse to run Turing simulations
which would require an infinite amount of memory.  Unfortunately, I know
of no proof for that -- clearly, the set of Turing machines which take
infinite memory is a subset of the Turing machine which do not halt.

>    William> Oh, and for an equally technical nit-pick: contrary to your
>    William> claim, none of the numbers in the range between 0.0 and 1.0
>    William> are infinite.  The cardinality of the set, OTOH, is
>    William> infinite and unbounded.

>This is pseudo-mathematical nonsense, I'm afraid.

Thanks, but please try not to hold back so much.  Let us know how you
*really* feel!

></off-topic pedantry>

<!-- I can't delete the closing tag, can I?  XML newsreaders would choke
;-). -->

>Graham Hughes <graham at ccs.ucsb.edu>

-- 
-William "Billy" Tanksley