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.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top