Understanding is compression

In Sections V and VI of his „Discourse on Metaphysics“, Leibnitz asserts that God simultaneously maximizes the variety, diversity and richness of the world, and minimizes the conceptual complexity of the set of ideas that determine the world. And he points out that for any finite set of points there is always a mathematical equation that goes through them, in other words, a law that determines their positions. But if the points are chosen at random, that equation will be extremely complex.
This theme is taken up again in 1932 by Hermann Weyl in his book “The Open World” consisting of three lectures he gave at Yale University on the metaphysics of modern science. Weyl formulates Leibnitz´s crucial idea in 5 the following extremely dramatic fashion: If one permits arbitrarily complex laws, then the concept of the law becomes vacuous, because there is always a law ! Then Weyl asks, how we can make more precise the distinction between mathematical simplicity and mathematical complexity ? It seems to be very hard to do that. How can we measure this important parameter, without which it is impossible to distinguish between a successful story and one that it is completely unsuccessful ?
This problem is taken up and I think satisfactorily resolved in the new mathematical theory I call algorithmic information theory. The epistemological model that is central to this theory is that a scientific or mathematical theory is a computer program for calculating the facts, and the smaller the program, the better. The complexity of your theory, of your law, is measured in bits of software:
Program-->Computer-->Output Theory-->Computer-->mathematical or scientific facts
Understanding is compression !
Now Leibnitz´s crucial observation can be formulated much more precisely. For any finite set of scientific or mathematical facts, there is always a theory that is exactly as complicated, exactly the same size in bits, as the facts themselves.
But that doesn´t count, that doesn´t enable us to distinguish between what can be comprehended and what cannot, because there is always a theory that is as complicated as what it explains. A theory, an explanation, is only successful to the extent to which it compresses the number f bits in the facts into a much smaller number of bits of theory. Understanding is compression, Comprehension is compression ! That´s how we can tell the difference between real theories and ad hoc theories. What can we do with this idea that an explanation has to be simpler than what it explains ? Well, the most important application of these ideas that I have been able to find is in metamathematics, it is in discussing what mathematics can or cannot achieve. You simultaneously get an information-theoretic, computional perspective on Goedel´s famous 1931 incompleteness theorem, and on Turing´s famous 1936 halting problem. How ?
You need an N-bit theory in order to be able to prove that a specific N-bit program is “elegant”.
You need an N-bit theory in order to be able to determine N bits of the numerical Value, of the base-two binary expansion, of the halting probability Omega.
Let me explain.
What is an elegant program ? It´s a program with the property that no program written in the same programing language that produces the same output is smaller than it is. In other words, an elegant program is the most concise, the simplest, the best theory for its output. And there are infinitely many such programs, they can be arbitrarily big, because for any computational task there has to be at least one elegant program.
And what is the halting probability Omega ? Well, it´s defined to be the probability that a computer program generated at random, by choosing each of its bits using an independent toss of a fair coin, will eventually halt. Turing is interested in whether or not individual programs halt. I am interested in trying to prove what are the bits, what is the numerical value, of the halting probability Omega. By the way, the value of Omega depends on your particular choice of programming language, which I don´t have time to discuss now. Omega is also equal to the result of summing ½ raised to powers which are the size in bits of every program that halts. In other words, each K-bit program that halts contributes 1/2K to Omega.
And what precisely do I mean by an N-bit mathematical theory ? Well, I´m thinking of formal axiomatic theories, which are formulated using symbolic logic, not in any natural, human language. In such theories there are always a finite number of axioms and there are explicit rules for mechanically deducing consequences of the axioms, which are called theorems. An N-bit theory is one for which there is an N-bit program for systematically running through the tree of all possible proofs deducing all the consequences of the axioms, which are all the theorems in your formal theory. This is slow work, but in principle it can be done mechanically, that´s what counts. David Hilbert believed that there had to be a single formal axiomatic theory for all of mathematics; that´s just another way of stating that math is static and perfect and provides absolute truth.
Not only is this impossible, not only is Hilbert´s dream impossible to achieve, but there are in fact an infinity of irreducible mathematical truths, mathematical truths for which essentially the only way to prove them is to add them as new axioms. My first example of such truths was determining elegant programs, and an even better example is provided by the bits of Omega. The bits of Omega are mathematical facts that re true for no reason and thus violate Leibnitz´s principle of sufficient reason, which states that if anything is true it has to be trues for a reason.
In math the reason that something is true is called its proof. Why are the bits of Omega for no reason, why can´t you prove what their values are ? Because, as Leibnitz himself points out in Sections 33 to 35 of “The Monadology”, the essence of the notion of proof is that you prove a complicated assertion by analyzing it, by breaking it down until you reduce its truth to the truth of assertions that are so simple that they no longer require any proof. But if you cannot deduce the truth of something from any principle simpler that itself, then proofs become useless, because anything can be proven from principles that equally complicated e.g. by directly adding it as a new axiom without any proof. And this exactly what happens with the bits of Omega.
In other words, the normal, Hilbertian view of math is that all of mathematical truth, an infinite number of truths, can be compressed into a finite number of axioms. But there are an infinity of mathematical truths that cannot be compressed at all, not one bit !

- Gregory Chaitin