Infinity and you (was Re: Turing Compliant?)
William Tanksley
wtanksle at dolphin.openprojects.net
Mon Sep 6 21:35:31 EDT 1999
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
More information about the Python-list
mailing list