From: Gareth McCaughan <gareth.mccaughan@pobox.com>
To: math-fun@mailman.xmission.com Sent: Sunday, October 14, 2012 5:18 PM Subject: Re: [math-fun] 3. Re: Another approximation of pi
On Monday 15 October 2012 00:12:21 meekerdb wrote:
pi has maximal Kolmogorov complexity.
What do you mean?
Surely the Kolmogorov complexity of a thing is the length of the shortest program that produces it? You can write a very short program that produces pi. Pi has very *small* Kolmogorov complexity.
But rational approximations to pi don't. Is there some way to define the minimum algorithm for computing pi to say N decimal places. And if so, what is the length of the algorithm as a function of N?
Ultimately constant, because for large N the best way to make a program that outputs N digits of pi is to make a program that outputs pi and look only at the first N digits.
(If you insist on having it stop at the right place, then it goes like constant + complexity(N); the second term looks like log(N) for almost all N.)
-- g
_______________________________________________
A program that calculates pi to N places requires memory that grows as some function f(N), and f(N) must grow unboundedly large with N. This is true for any irrational, since a finite state machine eventually repeats, and thus can only calculate rationals. So perhaps the complexity of an irrational number can be characterized by the slowest growing memory needed for its calculation. -- Gene