Xref: utzoo sci.math:9795 comp.theory:315 sci.logic:750
Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!swrinde!ucsd!ucrmath!x!baez
From: baez@x.ucr.edu (john baez)
Newsgroups: sci.math,comp.theory,sci.logic
Subject: Reflections on 50,000 digits of "e"
Message-ID: <3981@ucrmath.UCR.EDU>
Date: 9 Feb 90 19:34:38 GMT
References: <1528@milton.acs.washington.edu> <906@imec.UUCP> <31369@shemp.CS.UCLA.EDU> <15889@well.UUCP> <1990Feb3.062130.25362@cadence.com> <14353@cs.yale.edu> <1990Feb7.002735.8746@cadence.com>
Sender: news@ucrmath.UCR.EDU
Reply-To: baez@x.UUCP (john baez)
Organization: University of California, Riverside
Lines: 41

In article <1990Feb7.002735.8746@cadence.com> holsz@cadence.com (Wlodzimierz Holsztynski) writes:
>
>Just an example. Can we compress strings of bits (0-s and 1-s) of
>length 100, so that on average we get less than a 1000 bits? Many
>mathematicians will have a knee-jerk reaction. 

My knee-jerk reaction is that you made a typo and mean 100 in
both cases.  

It's not surprising that you can map the set of 100-bit
sequences 1-1 into the set of 100-or-fewer-bit sequences, since
there are about twice as many of the latter.

When dealing with binary expansions of arbitrary reals,
things are fairly different since there are uncountably 
many.  

I really wouldn't want to say one number is more
complicated than another, I would prefer to say its
decimal or binary expansion is more complicated, because
this is only one of many possible descriptions of the number.
It has the advantage of working for all real numbers
(though most are "inaccessible" since not computable),
but it's certainly not the best for many purposes, like
telling if they're rational.  "What?" you say, "The rationals
repeat and the irrationals don't".  True, but one can
never decide this from examination of a finite-information
piece (e.g. intial segment) of a decimal expansion.  If
one specifies a number as the solution of an equation - 
which takes a finite string - one can "often" decide
whether the number is rational.  I say "often" with
misgivings, because I don't know, for example:

1) is there a decision procedure for rationality of
algebraic numbers (i.e., given a polynomial with
integer coefficients, can one tell which roots are
rational and which not?  I flunked Galois theory :-)).
If not, is there one that works for some positive
density of cases???

2) how about other presentations of numbers?