Dr. Dobb's Python-URL! - weekly Python news and links (Mar 17)

[Tim Peters]

[Michael Hudson]
>>> <hand-waving>
>>> But for a number to be "known", it must be comptuable in some sense
>>> and there are only countable many Turing machines...
>>> </hand-waving>

[Tim]
>> That's an excellent argument for why we can't show an example of an
>> uncomputable real, but really no more convincing wrt normality than
>> wrt irrationality.

[Michael]
> Well, I guess.  But rationality seems a much more tractable notion
> than normality -- it seems "finite" in some sense.  I'm not sure
> rationality is that good an example, as having irrationals is somehow
> the point of the reals...  Transcendence would be a better example,
> but I'm an algebraist -- what's a transcendent number, again? <wink>.

I don't care about irrationality -- it was just an example of a property
other than uncomputability.  No matter what property P you have in mind, the
"but there are only countably many reals that can be 'known'" caveat
applies, and I don't see a reason to believe that sheds light unless P is
related to "unknowability" (in which case that the set of knowable reals is
countable is supremely relevant).  David Bailey et al. have gone quite a way
in understanding normality; see papers at his web site:

    http://www.nersc.gov/~dhbailey/


>>> Why does anyone care about normality, anyway?

>> I think because attempts to define what random means lead naturally
>> to normality.  If, e.g., pi is shown *not* to be normal, then it
>> would be very hard to believe it's random in any reasonable sense.
>> If it is shown to be absolutely normal, I expect reasonable people
>> would disagree about whether that's strong enough to conclude it's
>> random, though.

> Except that pi clearly *isn't* random...

Indeed, my wording there was too sloppy to bear.  pi isn't random, but its
decimal digits known so far pass extensive statistical tests for randomness.
That's interesting in itself, and if pi is shown to be absolutely normal
then there are a great many statistical tests for randomness we know its
digits will pass without bothering to apply them.  Of course there's at
least one computable statistical test the digits of pi don't pass, namely
the test that compares a sequence of digits against the computed digits of
pi.

> but this leads very quickly into the "the smallest integer than can't
> be described in less than 100 characters" type paradox, and I don't
> care about them, either :-)

The pseudo-random numbers produced by Python 2.3's Mersenne Twister are
provably equidistributed in 624 dimensions.  It's of supreme practical
importance if a cheesy little pi algorithm can do better than that <wink>.