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