By James Bailie, Australian National University
Suppose you and your friend each read a book on a difficult subject. You think your book is harder than your friend’s, but your friend thinks the opposite. How can you work out which one is more complex? Perhaps you could count up how many different words appear in each book and say the book with the largest number of different words is more complex. Or maybe you could try to make the book shorter, without losing any information. Then the book that can be made the shortest is the least complex.
But doing that sounds really tricky. Instead, why not get a computer to do it? There are computer programs, called compressors, that can make digital files smaller without losing information. This is what you do when you make a .zip file. Now, imagine you had the best compressor ever. It takes any file and outputs the smallest possible .zip of that file. To compare the difficulty of the your two books, you could run this compressor on the two books and say that the book with the biggest .zip would be the most complex.
This idea is called Kolmogorov complexity, which is named after the prolific Russian mathematician Andrey Kolmogorov. There is a huge range of applications of Kolmogorov complexity through maths, physics, biology and computer science. In particular, it is very useful in Artificial Intelligence. A robot often needs to learn about its environment so it can make the right decisions and actions. However, because of chance and randomness, this can often be very difficult. Sometimes the robot does the same action and gets different results. How does the robot work out how the world works? A good principle would be to choose the simplest model that explains all the things the robot has seen. How do you decide which is the simplest explanation? Well, it’s the one with the smallest Kolmogorov complexity!
The only problem with Kolmogorov complexity (and it’s a big problem) is that it is incomputable. That means it has been mathematically proven that the best possible compressor cannot possibly exist! There is actually no way to work out the size of the smallest .zip of a file, in general.
Despite this major drawback, Kolmogorov complexity is an extremely powerful idea. If you want to read more about it, try Li and Vitanyi’s book An Introduction to Kolmogorov Complexity and Its Applications. If you’re intrigued by the concept that certain computer programs cannot exist, then google the ‘halting problem’.