Infinity and you (was Re: Turing Compliant?)

[Graham Hughes]

>>>>> "William" == William Tanksley <wtanksle at dolphin.openprojects.net> writes:

<off-topic pedantry>

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

    >> 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.

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.

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.

    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.

It *is* true that no real number between 0 and 1 is `infinite', because
none of them are sets.  But it remains true that there are an `infinite'
number of numbers between 0 and 1 (exclusive), and yet each one is less
than 1 and greater than 0.  Thus the section of the real line (0, 1) is
`infinite' and bounded.

Since we're being pedants here, I will define what I mean by `infinite':
an `infinite' set is one such that the cardinality of the set is equal
to or greater than the cardinality of the set of all integers.

Calling the cardinality infinite is meaningless, because the cardinality
is a single value and not a set.  Calling it `infinite' is a
misapplication of concepts.  It *is* meaningful to state that the
cardinality of some set is greater than the cardinality of some other
set, and we may think of this as implying that one set is somehow
`bigger' than the other.

It *is* true that the cardinality of the set (0, 1) is greater than the
cardinality of any finite set, and it is true that the cardinality of
the set (0, 1) is greater than the cardinality of the set of all
integers, but none of this has anything to do with whether it is bounded
or not!

</off-topic pedantry>
-- 
Graham Hughes <graham at ccs.ucsb.edu>
GPG Fingerprint: 4FC5 80F0 63EB 00BE F438  E365 084B 4010 60BF 17D3
((lambda (x) (list x (list 'quote x)))
 '(lambda (x) (list x (list 'quote x))))