Complexity unveiled

A program is a string. The Kolmogorov complexity of an output s is the length of the shortest program that prints it on a fixed universal machine U:

Here the program is tiny: an elementary automaton's rule (8 bits), a seed (the bits of a word), and a loop that applies the rule row after row. Choose them below.

The automaton writes one row at a time. Read row after row and the output is a single one-dimensional thread of bits, which is how any machine actually executes: one step, then the next. Slide the control above to the left and you see the thread laid out as time; that is the familiar spacetime diagram.

A general-purpose compressor such as deflate only finds repetition. For Rule 30 it finds almost none and reports the thread as nearly incompressible. But the true description is tiny: the program is the compression, and$K(s) \le |p| + c_U$ where $c_U$ is the fixed cost of the interpreter. The bar marked |p| counts all of it, including the gzipped source of the loop that runs the rule.

Slide right and the same thread is folded into the square by a space-filling curve, a continuous surjection $f : [0,1] \to [0,1]^2$. Hilbert's curve visits every cell of a$2^k \times 2^k$ grid exactly once, and neighbours in the thread stay neighbours in the plane. As the order grows the path length diverges, $L_k = 2^k - 2^{-k}$, and its image fills the square: a one-dimensional line with Hausdorff dimension

Every bar above is an upper bound. Nothing can give the exact value: K is uncomputable. If a program could compute it, a short program could search for “the first string whose complexity exceeds a billion bits” and print it, a string described in far fewer bits than a billion. That is Berry's paradox turned into a proof.

The same wall appears everywhere at the edge of the taxonomy. The halting problem is undecidable (Turing, 1936).Rice's theorem extends it: every non-trivial property of what a program computes is undecidable.Chaitin's halting probability for a prefix-free universal machine,

is a well-defined real number between 0 and 1 whose binary digits are algorithmically random. Knowing its firstn bits would decide the halting problem for every program up to length n. The set of pairs$(s, k)$ with $K(s) \le k$ is recursively enumerable: you can confirm an upper bound by running a program, but no procedure can confirm there is no shorter one. That is why this page is filed under RE.

The colony behind this page is watching you. Your pointer, keys and scrolling are coded as symbols, and their Shannon entropy is your input variety. Ashby's Law of Requisite Variety (1956) says a regulator must command at least as much variety as the disturbances it absorbs, so the colony is steered until its own entropy tracks yours. Move restlessly and it grows turbulent; go still and it settles into still lifes.

This is second-order cybernetics in Heinz von Foerster's sense: the observer belongs to the system being observed. The page measures the reader measuring the page, and those measurements change what there is to see. It is also a small case of what Maturana and Varela called autopoiesis: the colony continually regenerates the pattern that keeps it going, and the site's job is only to perturb it, never to specify it.