MATH: (i.e. no longer funny) (was Re: [SPORK, FUNNY] Donald Rumsfeld... the poet?)

James Rogers jamesr at
Mon Apr 14 22:59:11 PDT 2003


Disclaimer:  I'm not a number theory guy.

My analysis after some consideration is that the set of real numbers with a
finite Kolmogorov Complexity is uncountable, since the transcendentals seem
to be uncountable yet do have a finite Kolmogorov Complexity (e.g. "e" and
"pi").  This alone pretty much seems to settle it.

The analysis is slippery though, mostly because of the indirection
surrounding the KC.  It took me a second to wrap my head around it.

To address another issue from below (re: limits and finite descriptions),
one of the primary differences between Shannon's and Kolmogorov's
information theory is that Kolmogorov views transcendentals and similar as
fundamentally finite beasties while Shannon generally does not. The
importance of this isn't immediately obvious for lots of things, but it is a
critical difference in certain areas of computational theory.


-James Rogers
 jamesr at

On 4/14/03 4:57 PM, "R. A. Hettinga" <rah at> forwarded:
> At first thought, that the "finitely  describable reals" should be countable
> seems correct.  Only finitely many statements of a given length possible, so
> list them all in order of length, and the list should provide a counting,
> QED.
> But why is e one?  Or pi?  For proper definition they both require a
> limiting process.
> And once limits are allowed into the class of processes of finite
> describability, the camel's nose is under the tent.  Because every real
> number is the limit of some sequence of rational numbers.  And the Cantor
> diagonal construction shows easily that any listing of those is not
> complete.
> So, you must accept that either the finitely describable numbers are
> uncountable or that they include some that are easily named.
> Which it is probably depends on the exact definition you choose for
> "finitely describable number."

More information about the FoRK mailing list