The shortest description nobody can certify

Which of these two is more random: a string of a thousand alternating bits, or a thousand tosses of a coin? Probability theory cannot say. Both have the same chance of $2^{-1000}$. Yet everybody can tell them apart, because one has a very short description and the other, as far as anybody can tell, does not. In the 1960s Ray Solomonoff, Andrey Kolmogorov and Gregory Chaitin independently turned that into a definition: the complexity of a string is the length of the shortest program that prints it.

The definition is clean, and it has an odd property. Nearly every string has high complexity, as a line of counting shows. And it is impossible to compute, as a line of diagonal argument shows. It is worse than that. A formal theory cannot prove that any particular string has high complexity, once a fixed threshold is passed, even though nearly all of them have. So the fact that almost every string is incompressible is true of almost nothing that can be pointed to. This essay computes what can be computed at the smallest scale, where the machines can all be listed, and shows where the computation has to stop.

All the small programs #

A definition by shortest programs needs a language, and the language used here is the smallest honest one. Take every Turing machine with $n$ states on a tape of two symbols, starting on a blank tape. Each state and symbol has a rule, which writes a symbol, moves left or right and goes to a next state or halts. There are $4(n + 1)$ possible rules per slot, and $2n$ slots, so that three states give $16^6 = 16{,}777{,}216$ machines. That is few enough to run them all.

It would seem that some might run forever, and this is the problem that no algorithm can settle. At three states it has been settled by hand, as the busy-beaver count describes: no three-state machine that halts takes longer than 21 steps. So anything still running after step 21 will never stop. This fact is what makes the census exact, and a fact of this kind exists for each size, but it is not computable. It takes all of the difficulty of the subject to know the size for even a few more states.

Of the 16.8 million machines, 7,571,840 halt, and between them they leave just 95 different strings on the tape. The bars in the figure rank these strings by how many machines produce them: 0 and 1 are left by 2,097,152 machines each, and 00 by 722,752. The longest are the rarest.

This suggests a measure. If a program were chosen at random, how likely is it to print the string $s$? Leonid Levin’s coding theorem of 1974 says that for a suitably universal language, this probability $m(s)$ determines the complexity up to a constant:

$$K(s) = -\log_2 m(s) + O(1).$$

That is, a string many programs produce must have a short one, because a random program finding it is like a random description hitting it. Jean-Paul Delahaye and Hector Zenil used this in 2012 to produce actual complexity estimates for short strings, by running small Turing machines exactly as is done here. Short strings are the case where compressors fail altogether, since a compressor’s overhead exceeds the string, so that the method fills a real gap. The strings 0 and 1 get 1.85 bits, and a string of six or seven bits with a complicated pattern gets about 20. Nothing here would be called a proof that those are the true values, since three-state machines are not remotely universal. They are simply the most honest numbers that can be calculated.

What Solomonoff wanted it for #

The earliest of the three authors was not thinking about randomness at all. Solomonoff wanted a theory of induction. Given the data so far, how should the next bit be predicted? His answer was to weight every program that fits the data by $2^{-\text{length}}$, and to predict by the weighted vote of what those programs do next. It is Occam’s razor stated as a formula, and it converges on any computable source faster than almost any other method. It also cannot be computed, for exactly the reasons given below, and yet its statement is what later methods of model selection, such as minimum description length, try to approximate. So the frequencies in the first figure are a crude version of a universal prior: they say which strings a mind with no other information should expect from a small machine. Bayes’s rule would then do the rest.

Why the language hardly matters #

If complexity depended on the language, it would be a fact about languages. But any universal language can run any other through a fixed interpreter, and this adds only the interpreter’s length. That is the invariance theorem: between any two universal languages, complexities differ by at most a constant. A property of strings emerges, up to that constant.

Machines of two and of three states are not exactly two languages, and neither is universal, but it is the nearest test available at this size. The two-state census has only 20,736 machines, of which 9,784 halt, with no machine later than step 6. Seventeen strings appear in both. Estimates from the two censuses have a rank correlation of 0.946. The same strings are ranked simple by a small set of machines and by one eight hundred times larger. The agreement is only suggestive, but it is close to what the theorem describes, and Soler-Toscano and others found much the same with far larger censuses at five states. A fair objection is that the constant in the theorem might be enormous. For short strings it is larger than the strings, so that complexity in the formal sense says nothing precise about any particular short string. Here, it should be read as a measure that is only meaningful in the limit, and the fact that it seems to behave at small sizes is a welcome surprise and not something promised by the theorem.

Most strings have no short program #

The counting argument takes one sentence. There are $2^n$ strings of length $n$, and the number of programs shorter than $n - k$ is less than $2^{n-k}$, so at most a fraction $2^{-k}$ of strings can be compressed by $k$ bits. So fewer than one string in a thousand can be compressed by ten bits, in any language at all. This is the same counting that underlies the size of most circuits. The census shows what it looks like in practice.

Every string up to length five is reached. At length six it is 26 of 64, at seven it is 7 of 128, and no machine leaves a longer one. Sixteen million programs produce only 95 outputs, because most of them behave identically, and the sharp fall-off is the counting argument in a concrete form. So a string that a machine this small can write is automatically special. This is one way to think about what randomness means. Per Martin-Löf showed in 1966 that a sequence passes every computable statistical test exactly when its initial segments cannot be compressed, which turns “random” from a feeling into a definition. It is also why the randomness that has to be earned has so much of the character of a resource.

What a compressor sees #

In practice, people measure complexity with a compressor. That gives an upper bound, since a compressed file and a decompressor make up a program. It is an upper bound and nothing more.

The compressor is LZ78, which builds a dictionary of phrases as it reads. A repeated 0110 goes to 0.173 bits per bit, and marking the square numbers goes to 0.116. Thue–Morse goes to 0.527, a surprisingly poor result for a sequence with a two-line definition, since a word that avoids repeats is built to frustrate the search for them. The digits of $\pi$ go to 1.186, and seeded random bits to 1.186. Compression has made them both longer, and the two are indistinguishable.

So the compressor rates $\pi$ as random, while a program of a few lines prints its digits to any length. The figure’s seeded random bits are the same, since the “random” generator is a short program and its seed. A true sequence of coin tosses would look identical in the figure and would almost certainly have no description shorter than itself. No test the compressor can apply tells these apart. This is not a defect of LZ78. In the limit, for computable statistics, a compressor can catch only the regularities it is been designed for, and it is a theorem that no computable compressor can catch them all.

The paradox as a program #

Why cannot complexity be computed? Suppose that $K$ were computable. Then this program would exist: go through all strings in order, and print the first with $K(s) > 1{,}000{,}000$. Its own length is a fixed amount, plus the digits of that million, and so a few hundred bits. And it prints a string whose shortest program has more than a million bits. That is a contradiction. It is the Berry paradox made exact: “the smallest number not nameable in fewer than twenty words” is named in fewer than twenty words. The paradox was just wordplay until “nameable” was replaced by “printed by a program”. Then it became a proof. It is the diagonal argument once again, in a very pure form. The word that cannot describe itself met the verbal version, and the program that prints itself supplied the trick that makes a program able to refer to its own length.

Chaitin saw in 1971 that the same argument gives something stronger, about proofs.

Take any sound, computably axiomatised theory. Consider this program: search through all proofs until one is found that shows $K(s) > L$ for some string $s$, and then print that $s$. The program’s length is a constant $c$, which depends on the theory, plus about $\log_2 L$ bits. If $L$ is much larger than $c + \log_2 L$, then finding such a proof would mean that a short program had printed a string that needs a long one. That is impossible for a sound theory, so the proof is never found. So no theory proves $K(s) > L$ for any string $s$, once $L$ is above a constant set by the theory itself. In the figure the constant is an illustrative 800 bits, and the crossing comes at 811. A real theory like ZFC would have a constant of some thousands of bits, perhaps.

It is worth spelling out how strange that is. Nearly all strings of a million bits have complexity near a million, and a proof exists of that fact, by counting. But for no particular such string can it be proved. Any specific string that anybody can write down, however random it looks, might have a very short program that nobody has found. This is a form of Gödel’s incompleteness theorem whose unprovable statements are abundant rather than specially constructed, and all of them are true.

How machines stop #

The census has one more thing to say about stopping. Of all three-state machines, 4,194,304 stop at their first step, exactly a quarter of the total, and 2,097,152 stop at the second. By step 10 only about two thousand stop. At step 21 just sixteen do. So almost all machines that stop do it almost at once, and a machine that is run for a few steps is not likely to stop at all. That is a small-scale view of a real phenomenon, studied by Cristian Calude and Michael Stay: most programs stop quickly or never.

Weighted over all sizes, the same distribution adds up to Chaitin’s number $\Omega$, the probability that a random self-delimiting program halts. It is a definite real number, and knowing its first $n$ bits would allow solving the halting problem for all programs up to length $n$. So its digits are about as dense with information as digits can be. They are incompressible: $K$ of the first $n$ bits is at least $n$ minus a constant. A theory can determine only finitely many of them, and Robert Solovay built a theory in which not a single digit can be determined. The machines that need a reason never to stop are the first few terms of it, and each new state’s worth of them is extremely hard to get. It is also striking that $\Omega$ is a number whose first digits, in some fixed language, have actually been computed, up to about 40 bits by Calude and others.

What this scale cannot show #

Three-state machines are not universal. Everything said here about $K$ applies to universal machines, and all the numbers in the figures come from something else. The census’s frequencies are only analogous to Levin’s $m(s)$. It also does not use self-delimiting programs, or weight by length, and it mixes all machines of a given number of states together. The rank correlation is on only seventeen strings, most of them very short, and it cannot support much. The compressor figure shows one compressor at one length, and a different algorithm would give somewhat different numbers.

Chaitin’s picture uses an arbitrary illustrative constant. Nothing here computes $c$ for an actual theory, and estimates of the size of such a constant are rough. Adam Yedidia and Scott Aaronson’s construction of a small Turing machine whose behaviour ZFC cannot determine, with 7,910 states, later reduced by others to well under a thousand, is the nearest thing to a real measurement of how far a formal theory can see.

What was computed and what was quoted #

The censuses cover every machine at two and three states, starting on a blank tape, up to the limits 6 and 21, which are quoted busy-beaver values and were checked by observing no halting beyond them. All counts follow from those runs: 20,736 and 16,777,216 machines, 9,784 and 7,571,840 halting, and 95 distinct strings at three states. The bits are $-\log_2$ of the shares. The correlation is a Spearman rank coefficient on the strings common to the two. LZ78 was run on 20,000 bits of each sequence, with the digits of $\pi$ computed exactly by Machin’s formula.

Chaitin’s argument is given in full, with an illustrative constant. Quoted: the theorems of Levin, Kolmogorov, Solomonoff, Martin-Löf and Solovay, Delahaye and Zenil’s method, the facts about $\Omega$, and the Yedidia and Aaronson construction.

Still open: where the constant actually is #

How large is the constant in Chaitin’s theorem for an actual theory, and what does it depend on? Known estimates vary widely, because the constant depends on how a theory is encoded and which universal machine is chosen, and it is not even clear what a canonical answer would be. There is a related question in which short strings have low complexity. The method of small machines has mapped strings of up to about twelve bits. How far this can go depends on busy-beaver values, and at five states these were finally settled in 2024 by an international collaboration of amateur and professional mathematicians. Six states have already produced machines that are beyond every computation, and the census stops there for good.

There is also a large open problem in the time-bounded version. The time-bounded analogue $K^t$ can be computed, slowly. Whether computing it is hard in a precise sense is equivalent to whether one-way functions exist, as Yanyi Liu and Rafael Pass showed in 2020. So a problem about short programs turns out to be tied to whether cryptography is possible at all.

A definition that cannot be used #

Complexity is defined as the length of the shortest program, and a count shows that nearly all strings have no short one, while a diagonal argument shows that no algorithm can find it, and no theory can prove it large for any one string. Listing every small machine gives the only direct view there is: 95 strings from sixteen million programs, and frequencies that agree on which strings are simple.

Past that scale, it is all upper bounds. Any program is evidence that a string is simple, and nothing can be evidence that it is not. It is a strange kind of definition, exact and central to the theory of randomness, whose values can almost never be known. That the digits of $\pi$ look random to any compressor, and that a few lines print them, is what that gap looks like from the outside.