Kolmogorov Complexity of a mathematical object is defined as the length of the shortest possible computer program needed to describe it. For computer scientists, Kolmogorov Complexity which is also known as Algorithmic Complexity is a measure of how compressible a mathematical object is. For example, we may be dealing with text (string of characters) or image (string of numbers), or any type of data and we are tasked to find the best compression algorithm. This is not an easy task.
Kolmogorov Complexity cannot be computed for most objects but approximations of it allow us to quantify randomness and structure in a different way.
I thank Jordana Cepelewicz at the Quanta Magazine for her article titled “Mathematical Simplicity May Drive Evolutions’s Speed” for reminding me about the Algorithmic (Kolmogorov) Complexity. One of the mathematicians featured in that article is Gregory Chaitin. I have met him many years ago in a seminar in NYC. He has many insights that deserve to be explored.
One of the ideas mentioned in the article is the idea that algorithmic complexity decreases asymptotically as evolution proceeds. I definitely think that this lead should be explored. At the end of the article G. Chaitin is quoted as saying “The idea of thinking about life as evolving software is fertile.” I find that statement very intriguing as well.
Additional Reading on Kolmogorov Complexity
The scientific journal Entropy has a special issue on Kolmogorov Complexity. The papers there are open access.