Working with the set of real numbers

Marko Rauhamaa marko at pacujo.net
Thu Feb 13 20:47:48 CET 2014


Chris Angelico <rosuav at gmail.com>:

> On Fri, Feb 14, 2014 at 1:00 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
>> Well, if your idealized, infinite, digital computer had ℵ₁ bytes of RAM
>> and ran at ℵ₁ hertz and Python supported transfinite iteration, you
>> could easily do reals:
>>
>>         for x in continuum(0, max(1, y)):
>
> How exactly do you iterate over a continuum, with a digital computer?

How "digital" our idealized computers are is a matter for a debate.
However, iterating over the continuum is provably "possible:"

  http://en.wikipedia.org/wiki/Transfinite_induction

> it would take a finite amount of time to assign to x the "next
> number", ergo your algorithm can't guarantee to finish in finite time.

My assumption was you could execute ℵ₁ statements per second. That
doesn't guarantee a finite finish time but would make it possible. That
is because

   ℵ₁ * ℵ₁ = ℵ₁ = ℵ₁ * 1

This computer is definitely more powerful than a Turing machine, which
only has ℵ₀ bytes of RAM and thus can't even store an arbitrary real
value in memory.


Marko



More information about the Python-list mailing list