# Should Kolmogorov complexity include all resources or just program size?

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.

• 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. – D.W. Jan 15 '16 at 3:41
• 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? – John Z. Li Apr 24 '19 at 3:36

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.