2
$\begingroup$

I've been thinking about pi and Kolmogorov complexity (Kc).

As the digits of pi are randomly distributed (and infinite) , they can't be compressed with a typical compression program. Through the prism of Kc, it would seem that a generating program (e.g. Gauss-Legendre algorithm) is much smaller than the output sequence hence characterising pi as not random.

The usual semantics revolving around Kc only mention program size so the above definition holds. Running the Gauss-Legendre algorithm comes at the cost of huge storage, processing power and some electricity. These resources increase (towards infinity) in some relation to the number of digits generated. If Kc is redefined as overall resources and not program size, pi becomes random.

Should Kc be restated as being resource based and not solely program size based, or is that an abstraction too far?

P.S. This is not a question of whether pi is random, but about a definition of Kolmogorov complexity.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Nitpick: the digits of pi aren't random at all; they are fixed. They do have various properties that you'd expect random digits to satisfy, such as a near-uniform distribution, etc., and they do look approximately "pseudorandom" in an informal sense. $\endgroup$
    – D.W. ♦
    Commented Jan 15, 2016 at 3:41
  • 1
    $\begingroup$ This is actually a very interesting question. The question can be rephrased as the following: How much negative (thermodynamic) entropy does one need to generate a string of fixed Kolmogorov complexity? $\endgroup$
    – John Z. Li
    Commented Apr 24, 2019 at 3:36

1 Answer 1

Reset to default
6
$\begingroup$

Should Kc be restated as being resource based and not solely program size based?

No. If you change the definition like that, you get a different concept, and the different concepts deserves its own different name. If you want to examine that concept, you should give it its own name. Kolmogorov complexity is a standard term with an accepting meaning; trying to "change" its meaning would only cause confusion.

Instead, if you want to study that alternative concept, give it a new name, and then study its properties. There's no need to change the existing definition of Kolmogorov complexity: Kolmogorov complexity is an interesting and useful concept to have in one's vocabulary. Removing it from our mental toolbox would only make our intellectual scope poorer.

To give you an analogy: If curves of the form $y=ax^2+bx+c$ are more useful in a practical application than lines, should we re-define the term "linear" to mean a function that can be expressed as $y=ax^2+bx+c$? No, that would only cause confusion. Instead, we give a different name (quadratic) to the different concept.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.