Algorithmic Randomness

In the [YOU] on AI Field Guide

The cycle that began with [YOU] on AI invites its readers to develop accurate beliefs about what AI can and cannot do. Algorithmic randomness supplies a precise account of one class of permanent limitation: the things the machines cannot learn, not because they are not yet capable but because there is nothing there to learn. When AI sceptics note that these systems fail at genuinely novel problems—problems that fall outside the distribution of their training data—they are, without the vocabulary, pointing at the randomness wall. Novel problems are, relative to the model’s training, incompressible: the model has no short description of them, because the structure that would ground a short description was not present in the data the model compressed. This is not a failure of scale. It is the correct response of a compression machine to patternless input.

The concept also clarifies the distinction between two very different kinds of incompressibility that are deeply important for the cycle’s humanistic project. The meaninglessly random string and the irreplaceably particular person are both incompressible in Kolmogorov’s sense: neither can be shortened without loss. But the random string is incompressible because it is empty of structure, while the particular person is incompressible because their structure is unique and unrepeated. A compression machine cannot distinguish these two cases. Both register simply as residue, as noise. This is the seam where Kolmogorov’s theory of intelligence meets the question of meaning: the machine cannot tell the accidental from the irreplaceable, the noise from the singular, the patternless from the person.

Origin

The concept emerged from Kolmogorov’s 1965 paper as a direct consequence of the definition of complexity: if an object’s complexity equals its length, no compression is possible, and the object is algorithmically random. Per Martin-Löf gave the concept its most mathematically precise formulation in 1966, defining random sequences as those that pass every computably enumerable statistical test—a characterisation that connects algorithmic randomness to the classical intuition of randomness as the absence of detectable pattern, while grounding it in the theory of computation rather than in probability.

The uncomputability of the randomness wall is a corollary of the uncomputability of Kolmogorov complexity: you cannot, in general, certify that a given string has no shorter description, because the space of programs is unbounded and undecidable. The wall is known to exist; its exact location for any particular string is in principle undeterminable. This creates the paradoxical situation of knowing the limit is real, knowing most of the territory lies behind it, and being unable to draw the boundary on a map.

Key Ideas

Randomness as object property. Classical probability theory assigns probabilities to events; it cannot characterise the randomness of a single object without reference to an assumed source distribution. Algorithmic randomness makes the characterisation intrinsic: the randomness is in the string, independent of how it was generated or what distribution it was drawn from. This is the conceptual move that makes the theory relevant to individual cases rather than to statistical ensembles.

The permanent wall. Learning extracts patterns. Where there is no pattern, there is nothing to extract, and no algorithm can change this. A learning machine confronting algorithmically random input will do no better than chance, not because of a failure of the machine but because the task is provably impossible. The discourse around AI that treats every limitation as a temporary obstacle awaiting the next breakthrough lacks the category of permanent structural limit that algorithmic randomness provides. Some things cannot be predicted, and the reason is mathematical, not technical.

Most objects are random. By a counting argument: the number of binary strings of length n is 2^n, while the number of programs of length shorter than n is less than 2^n. Therefore most strings of any given length have no shorter description—they are, in Kolmogorov’s sense, random. The learnable world is a minority of all possible worlds. Intelligence finds so much structure in the observable world not because structure is the rule but because the slice of possibility that physical and biological processes have produced happens to be unusually ordered. The success of learning is a fact about the world, not only about learning.

Overfitting as randomness error. In practice, every dataset mixes signal (compressible, structured, lawful) with noise (incompressible, random, accidental). The art of machine learning is to compress the signal without compressing the noise—to find the law and stop before encoding the accident. Overfitting is, in Kolmogorov’s terms, the error of treating incompressible accidental features of a training sample as though they were compressible lawful regularities. Algorithmic randomness is not only an outer limit on learning but an inner discipline within it: the learner must know when to stop, must refuse to compress what cannot be compressed.