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