HELP: restore my faith in Python

Moshe Zadka moshez at math.huji.ac.il
Tue Mar 7 06:56:20 CET 2000


On 6 Mar 2000, Neel Krishnaswami wrote:

> > Ahh, it's time to include extensions of the rational field. Let's get
> > more abstract. Abstraction is beautiful! And we need to represent 
> > transcendental numbers consistently aswell.
> 
> Is this possible? I've forgotten most of my analysis, but I was under
> the impression that you could divide the continuum as follows:
> 
>   o Rationals -- eg 2/3. Countably infinite.
>   o Algebraic irrationals -- eg sqrt(2). Countably infinite.
>   o Transcendental numbers -- everything else. Uncountably infinite.

Yes, but you can only "talk about" a countable number of them: the
constructive reals.

Definition:
A real number x is constructive (wlog assume that 0<=x<1, otherwise take
x%1) iff there's a recursive function f s.t.

	f(n)==0 iff the n'th bit in the binary expansion of x is 0

Or, in other words:
     oo
x = sigma [(1/2)**n]*f(n)
     1

Exercise: find an example of a non-constructive real. (It's easy: there
are uncountably many of them, as opposed to a countable number of
constructive reals)

> but the full transcendentals are just plain impossible. 

Constructive trancendentals are possible. If you don't mind never knowing
if a calculating some bit sticks your program in an infinite loop (halting
problem anyone?)

--
Moshe Zadka <mzadka at geocities.com>. 
http://www.oreilly.com/news/prescod_0300.html





More information about the Python-list mailing list