Recently, there have been many news stories in the science media about advanced AI programs creating new math. See here, here, and here, for example. Programmer Eric Holloway explains how the Kolmogorov complexity problem prevents AI from creating new math:

First, Kolmogorov complexity (KC) is the length of the shortest program that generates a bitstring. The Kolmogorov complexity of a random bitstring will be the same length as the bitstring. But a compressible bitstring, which has KC less than its length, will have structure.

Second, no program can increase its KC. Otherwise, the bitstring it generates will have KC greater than the length of the generating program, which contradicts the definition of KC. So, KC limits the information in a program.

How does KC limit AI?

Now, in one sense it seems KC is irrelevant when it comes to AI-generated math. Just about all of mathematics can be proven by the few axioms of set theory. This means we only need a short program to list all possible proofs from set theory, and consequently this program will generate almost all existing mathematics. Since set theory is consistent, then so will the list of proofs be.

Additionally, the proof list covers most math, so is complete for all practical purposes. So, the list of all proofs containing most mathematics has a negligible amount of KC, and obviously we just leave the short program running to generate all future mathematics as well. KC does not prevent AI from generating all current and future math!

All I have to do now is publish this short program and the AI industry can cut me in on their trillions of dollars!

But there a catch in here, isn’t there?

To see the problem, let’s imagine I generate a long set theory proof randomly. This proof will without a doubt be the first of its kind in the history of human civilization, the universe, or perhaps even the metaverse. New math! AI generated!

Will anyone care? No!

That’s because almost all the proofs in the list are useless random noise. The key is not that we can prove things, but that we know what things are worth proving.

It is like flipping a coin 1000 times. What if the sequence has never been seen before in the history of the universe? Why should anyone care?

Instead, imagine that I create a coin flip sequence that accurately predicts tomorrow’s lottery jackpot. Now, suddenly everyone cares!

However, the lottery sequence is random, so it contains new Kolmogorov complexity. Hence, a small coin flip listing program, like the set theory proof generator, will not be able to generate just the specific winning sequence. Instead, the flip lister will create an infinite list of flips.

It will indeed contain the winning lottery number, but most of the numbers will be losing numbers. Consequently, they are useless for predicting the lottery.

New math would be a predictor for a winning lottery number. Therefore, new math requires an increase in Kolmogorov complexity. But all forms of AI are programs and programs cannot increase their Kolmogorov complexity. Consequently, they cannot create new Kolmogorov complexity. Therefore, AI is fundamentally incapable of creating new math.

So why do the new AI math solutions matter to so many people?

The real reason many care so much about AI generated math is a commitment to recursive self improvement (RSI). It is the belief that AI is destined to eclipse all humanity, evolution, and all of physical existence. The point where AI takes the wheel from its human creators and starts improving itself exponentially without limit.

RSI is the holy grail of AI research. It is the cornerstone of the the Singularity religion.

Thus some will respond to what I have written by saying, so what? AI still is creating results that us slow humans can’t create or even comprehend!

Which brings us back to the catch…

Just as the inventions of AI up till now have relied on new math, it is reasonable to expect future progress, let alone unlimited exponential progress, will continue to require new math.

But new math means new Kolmogorov complexity. And AI, being a program, cannot create new KC, AI will forever be incapable of limitlessly improving itself. The pursuit of RSI is nothing but the largest waste of human capital in all of history.