From: ichudov@algebra.com
Date: Mon, 20 Jan 1997 08:13:58 -0800 (PST)
To: Cypherpunks <cypherpunks@toad.com>
Subject: Re: [Math Noise] (fwd)
Message-ID: <199701201613.IAA12459@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


Jim Choate wrote:
> Forwarded message:
> 
> > Only countably many real numbers, or members of any uncountable
> > set, are denumerable. It is the property of being uncountable,
> > rather than of being real or complex, which is important here.
> 
> In short you are saying there are Reals which can not be expressed in the
> format:
> 
>      AmEm + Am-1Em-1 + ... + A0E0 . B0E-1 + B1E-2 + ... + BnE-n+1

All reals are equivalent to sequences of digits, but there are reals such 
that there is no algorithm to generate their digits.

It happens because there are "more" real numbers than algorithms.

> > In general, only countably many members of any uncountable set
> > can be precisely specified within any formal system, given names
> > comprised of strings of symbols, or other similar things.
> 
> And I contend that ANY number which is Real can be expressed by the decimal
> expansion above. Which clearly qualifies as a formal system.

I suggest the following mental exercise. FORGET FOR A MOMENT ABOUT 
REAL NUMBERS. Let's deal with mummies: 

DEFINITION: I define a mummy as possibly infinite sequence of
characters, separated by one dot, such that only characters abcdefghij
are allowed. Also, mummies that are represented by finite sequences of
characters are by this definition equivalent to mummies that end
with an infinite sequence of letters "a". END DEFINITION.

Examples: 

dce.abdefhaabdaaa
ae.cacacacacacaca... 

and so on.

Obviously, some of the mummies, such as c.cccccc... (with an ininite 
sequence of "c") CAN be generated by algorithms.

The interesting fact, that i will prove below, is that some of
them cannot be generated by any algorithm.

THEOREM: The set of mummies is more than countable
PROOF: if it is countable, we can construct a mummy that is not counted.
it is easy.

THEOREM: there are mummies such that there is no algorithm that
can print them. 
PROOF: the set of mummies is more than countable, the set of algorithms 
is countable, therefore there is no way to construct a one-to-one
correspondence between mummies and algorithms.

Do you agree?

Now let's back to the original problem of real numbers: the only
difference between mummies and real numbers is that digits 0123456789
are replaced by characters abcdefghij. 

Not a whole lot of difference, so everything that applies to mummies
applies to real numbers.

	- Igor.