On 10/14/2012 5:18 PM, Gareth McCaughan wrote:
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.
Sorry, brain fade there.
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.)
The shortest program to output pi is probably longer than the shortest program to output 3.14, so I'm wondering how the length increases with the number of decimal places. Are approximations like 31^(1/3) actually computationally efficient? Brent