What did you dream of doing when you were 16 years old? I wanted to drive a car and travel the world. But American mathematician Ray Solomonoff had more ambitious goals at that age. He wanted to find a method to solve every conceivable scientific problem.
This was not just wishful thinking—the teenager had a groundbreaking idea that would establish a completely new field of research. Over the next few years, Solomonoff developed a concept that made it possible to systematically search data for patterns—and thus reveal the hidden processes that underlie our world.
Today this may be reminiscent of the way artificial intelligence works. But Solomonoff formulated his first ideas in 1942—long before AI algorithms existed. Solomonoff’s approach was based on the principle of Occam’s razor, according to which the simplest explanation for a phenomenon is usually the correct one. (Physicists employ the same logic; they seek the simplest formulas to try to describe as many physical processes as possible.)
On supporting science journalism
If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Solomonoff was looking for a set of rules or an algorithm that would reveal hidden relationships in data. In this way, he hoped, everything in the world could be simply explained. For example, if you record the trajectory of a thrown baseball, you can find any number of mathematical formulas—some very complicated—that reproduce the course of the trajectory. To derive the correct law from all these possibilities, you should look for the simplest description. The answer will most likely correspond to Newton’s laws of motion, which describe the interaction of two forces: the force with which the person threw the ball and the gravitational force that brings the ball to the ground.
Solomonoff was looking for a rule that would select the simplest of all possible descriptions. Such a rule could be translated into a computer program. Any data could be passed to this program, and after a certain amount of time, the simplest explanation for the origin of these values could be obtained. It would be a veritable miracle machine.
How to Define “Simple”
First things first: Solomonoff’s simplest-description finder does not exist—and it never will. Nevertheless, with his ideas, the then 16-year-old stood at the precipice of a completely new field of research that deals with the true nature of chance and complexity. And as is so often the case in the natural sciences, two other people had quite similar ideas at about the same time.
One of these people was Soviet mathematician Andrey Kolmogorov, who was primarily concerned with probabilities and random numbers. In particular, he was interested in how to decide whether the description of a phenomenon is simple or complicated.
Let’s say I show you the number 25,041,903. At first glance, it seems pretty random. There are various ways to explain how I obtained this value. For example, I could have used a random-number generator and obtained the digits 2, 5, 0, 4, 1, 9, 0 and 3, in that order. This doesn’t seem particularly satisfactory—there isn’t a reasoning behind it that helps you remember the value. But I could instead say that this number is equal to the product of the three primes 3 x 61 x 136,841. Or I could tell you that the sequence of numbers starts at the 40,122,575th decimal place of pi or that I chose this number because Kolmogorov was born on April 25, 1903. Which of these explanations sounds the simplest to you? Different people will probably have different replies.
Kolmogorov succeeded in developing an objective method to determine the complexity of objects. The Kolmogorov complexity of a number corresponds to the length of the shortest computer program that calculates the number. The shorter the program, the simpler the number.
The Kolmogorov complexity thus depends on the programming language used. A certain program might turn out shorter in Python than in C++ and vice versa. Every computer program can be expressed in machine code, which in turn consists of a sequence of 0’s and 1’s. The length of the shortest sequence of 0’s and 1’s for which a computer calculates the desired result corresponds to the Kolmogorov complexity.
So if you want to determine the Kolmogorov complexity of 25,041,903, you can translate the various explanations (that it is a result of digit enumeration or prime factorization, a position in pi or the date of Kolmogorov’s birthday) into a computer program and count the characters required in the corresponding machine code.
And my earlier examples might have excluded an even simpler explanation for 25,041,903. Kolmogorov developed a systematic way to identify the shortest program. To do this, you give a computer a number, such as 25,041,903. The computer then runs through all possible algorithms one by one—starting with the smallest, which is coded with a 0 or 1. The computer does this until the formulated programs produce the desired result. The first program that returns the value 25,041,903, for example, is then the shortest. Its character length corresponds to the Kolmogorov complexity of 25,041,903.
A Pesky Paradox Destroys the Dream
At first glance, Solomonoff’s dream now seems to have been realized. With Kolmogorov complexity, it seems like any pattern in any data can be revealed.
But a paradox puts a wrench in the works. Philosopher Bertrand Russell attributed the problem in question to librarian G. G. Berry in 1908 —long before Solomonoff and Kolmogorov published their ideas. An example of Berry’s thought experiment is as follows: Suppose you have a dictionary with just 20 words, and you try to describe different numbers using these words—very similar to what Kolmogorov had in mind with computer programs. You can start to gradually define numbers using these 20 words. There are only a finite number of ways to combine the 20 words, so you can only describe a finite number of numbers. Because there are an infinite number of numbers, however, some of them will escape such a definition; you will eventually arrive at a number that cannot be described in just 20 words. But what if you use some of the 20 words to formulate the description “the smallest number that cannot be described in 20 words or less”?
This definition comprises only 12 words, creating a contradiction. What has gone wrong? It turns out that you cannot calculate how many words are needed to define a number. This seems like a cheap excuse at first, but in fact, the Berry paradox and Kolmogorov complexity are related to one of the most unintuitive features of mathematics: some truths cannot be proven. Or to put it another way: mathematics is incomplete.
Suppose there really is a computer program K that calculates the Kolmogorov complexity associated with each input. This program consists of one million characters. It does not have to be fast or efficient; it just has to work.
Now test the program and feed it with all possible inputs until you finally find a large number x whose complexity is two million. Then proceed in a similar way to the Berry paradox. You write a new computer program P that performs the following task: it systematically goes through all the strings and uses the program K to calculate the Kolmogorov complexity of the strings until it finds one with a complexity of two million.
The new program P depends directly on K and will therefore not contain many more characters than K. (In any case, it consists of less than two million characters.) But this means that a computer program with fewer than two million characters has been found that calculates a number with a complexity of two million—a contradiction.
If a logical argument generates a contradiction, at least one of the assumptions must be false. In this case, we have assumed that there is a program K that calculates the Kolmogorov complexity for every input. Therefore, there is only one possible conclusion: such a K cannot exist. It is impossible to find the shortest program that generates this input for every conceivable input.
A Happy Ending Is Possible Nonetheless
So 16-year-old Solomonoff’s dream was not realized. But even if the Kolmogorov complexity cannot be calculated for every input, the idea proves useful in many applications. Most special cases do not require an exact Kolmogorov complexity—an approximation will suffice. Experts usually use compression programs for this. In situations that call for Kolmogorov complexity, “you can instead feed your data into a compression program, say using gzip or saving your image as a .gif file, and use that as a crude approximation,” computer scientist Scott Aaronson of the University of Texas at Austin told Plus.
For example, if you want to find out whether two sequences of numbers, x and y (which can correspond to measurement data, for example), are related, you can first compress x and y individually and then append both sequences together and compress xy. If the compression of xy is barely greater than the individual compressions of x or y, then there must be correlations between the number sequences—and you have clues to hidden patterns.
Kolmogorov complexity can also be used to determine how random a particular sequence of numbers is. For example, the three eight-digit numbers 25,041,903, 47,395,929 and 10,101,010 could have been generated by a random-number generator—even if they do not all appear to be equally random. The probability of generating each of these three numbers by chance is the same: in the number range from 00000000 to 99,999,999, there is a probability of 1 in 108 that you will come across one of these values. But 10,101,010 has a clear pattern, as does 25,041,903, which corresponds to a date of birth. By calculating the Kolmogorov complexity of the numbers, it is possible to assess whether they follow a certain pattern—and whether a random-number generator works reliably.
Unfortunately, Kolmogorov complexity does not answer the question of “life, the universe and everything.” If we are to believe science-fiction author Douglas Adams, then the answer to that question is 42. But curiously, the number 42 is not particularly complex—it can be calculated using the Kolmogorov complexity.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.