Kolmogorov complexity
Imagine you’re on the phone to a friend, and you need them to redraw a picture of 64 black and white squares exactly as you see it. If the squares simply alternate black, white, black, white, you’re done in a few words (one, zero, repeated) and your friend can fill in every square without any more help. If the squares were set by flipping a coin, though, there’s no shortcut, and you have to read out all 64 of them in order.
In 1965 the Soviet mathematician Andrey Kolmogorov turned this into a measure, and Ray Solomonoff and Gregory Chaitin arrived at the same idea independently around the same time. The Kolmogorov complexity of something is the length of the shortest set of instructions that reproduces it exactly. The instructions are written as a computer program, so that nobody can cheat by leaving details to the reader’s imagination, or by leaning on a word like “checkerboard” that only works because both of you already know the pattern. The stripes need a program only a line long, while the coin flips need a program that simply contains the whole picture, so their description is as long as the thing itself.
The trouble is that two of these pictures look equally random, yet one comes from a short rule. You can only tell them apart if you already know the rule, so you need to see the full inner workings of whatever made the pattern. For almost everything we want to study, we can’t.
Even when you can see the full inner workings, there’s a second problem. The length of a program depends on which programming language you write it in. And there is no universal “right” language. Worse, Gregory Chaitin showed (building on Gödel) that you can never prove a pattern has no shorter description, so you can’t ever be sure you’ve found the shortest program.
Logical depth
Go back to the phone call, but this time you’re reading out 32 letters of DNA, each one an A, C, G or T. The first strand is just AT over and over, so it’s quick to say. The second was picked at random, and the third is the start of the human gene that makes insulin. Neither of those has a shortcut, so you read out every letter, and from the letters alone your friend couldn’t say which one was random and which one came from a living thing.
The difference is in where they came from. The random strand has no past beyond a few rolls of a die. The gene is the latest in a line of copies stretching back about four billion years to the first life, each copied from the one before with a change or two, and kept only if it still worked.
In 1988 the IBM physicist Charles Bennett turned this into a measure, with life as the example he had in mind. The logical depth of something is how much work it takes to produce it from the simplest possible starting point. The gene is deep, because the simplest way to arrive at a working genome, where every part has to fit with every other, is in effect to replay its evolution. The repeat is shallow, since it’s one short rule applied over and over, and so is the random strand, because there’s nothing to work out: you just write it down.
This is where depth meets Kolmogorov complexity. Bennett’s simplest starting point is the same shortest program that Kolmogorov complexity is about, but where Kolmogorov asks how long that program is, depth asks how many steps it takes to run. So one is the length of the recipe and the other is the cooking time.
The problem is that depth is built on the shortest program, i.e. when faced with a real system, you still can’t tell a deep pattern from a random one just by looking.
Hierarchical complexity
Imagine two watchmakers. The first builds each watch in one go, so whenever he puts one down to answer the phone it falls to pieces. The second builds stable pieces of ten parts, then pieces of ten of those, then the watch, so an interruption costs much less.
Herbert Simon told this story, about watchmakers he called Tempus and Hora, in his 1962 essay The Architecture of Complexity. He argued that anything complicated is built up a bit at a time, whether by a watchmaker or evolution. Therefore, most complex systems will always be made of nested stable pieces.
Simon never turned this into a number, but the biologist Daniel McShea did. In a 2001 paper he scored living things by how many layers of once-independent things are nested inside them, and that count is their hierarchical complexity. A bacterium scores 1, a cell carrying mitochondria (once free-living bacteria) scores 2, a body of such cells scores 3 and a colony that acts as one scores 4. In 2017 McShea, Noel Heim and colleagues showed that the size of the largest living things, which has grown about a billion billion times, rose mostly in two jumps of level: when cells with mitochondria appeared around 1.9 billion years ago, and when bodies of many cells took off around 600 million years ago.
Simon also noticed that hierarchies tend to be nearly decomposable, with each part tied strongly together inside and only weakly to the others, like rooms in a building where heat evens out within a room in hours but takes a week to cross the walls.
The weakness comes from the subjectivity in first defining what counts as a level, and in deciding when to stop counting turtles on the way down. But there are also plenty of examples which break this intuition. For instance, slime mould is an extremely simple organism, yet it exhibits extraordinarily complex behaviour. Similarly, an often defining feature of complex systems is that they have to be treated holistically rather than through reductionism. Decomposing the brain doesn’t make sense, for example. You can identify elements like the hippocampus, but those elements aren’t stable, in that they don’t work without the rest of the brain.
There is an emerging consensus that we should call systems like Simon’s complicated rather than complex.
Assembly theory
Imagine making a word out of letter tiles, where each step glues two pieces together. You start with loose letters, and anything you’ve already glued together you can use again as often as you like, as though it came off a copier. Building ABRACADABRA one letter at a time takes ten steps, one for each letter after the first. But once you have ABRA you can glue it straight onto the end of ABRACAD instead of spelling it out a second time, and that brings the whole word down to seven steps.
The chemist Lee Cronin introduced this idea in 2017, with molecules in mind rather than words, and developed it with the astrobiologist Sara Walker into assembly theory. The assembly index of an object is the fewest joining steps it takes to build from its basic parts, when anything made along the way can be reused. For a molecule the parts are its chemical bonds, and each step joins two fragments together at an atom they share. This obviously builds on logical depth, by giving concrete counts of physical steps.
That change makes it the first measure on this page that can be taken in a lab. A mass spectrometer smashes molecules apart and weighs the fragments, and the more different fragments a molecule breaks into, the more steps it must have taken to put it together. In a 2021 study, Cronin, Walker and their colleagues measured samples ranging from rocks and seawater to yeast and beer, and found that molecules with an index above about 15 only turned up in samples that were alive or had been made by life. That makes it a candidate for searching for life on other planets without having to guess what that life’s chemistry would look like.
A single complicated object could still be a fluke, the way a long string of coin flips is, so the theory also counts how many identical copies there are. Chance can occasionally make something complicated, but it can’t make the same complicated thing over and over again. If you find thousands of copies of a molecule with a high index, something must be remembering how to make it, whether that’s a cell copying its genes or a factory following a recipe. Cronin and Walker treat the two numbers together, in a quantity they call assembly, as a measure of how much selection it took to produce what you’re looking at.
This is a fantastic measure for finding life and a real practical step forward with logical depth. But it is extremely orientated toward physical objects. Conceptual models like the economy are much harder to quantify. It also suffers the same problem as hierarchical complexity, in that the brain is extremely complex, but because its core parts are reused (i.e. neurons), the brain would score relatively low on this measure.
Statistical complexity
Go back to the phone call one last time. Now your friend has to guess each square before you read it out, and the question is how much they need to keep in mind to guess as well as anyone could. For stripes they only need to remember whether the last square was black or white. Another pattern runs black then white then a coin flip, over and over, and for that one they need to know where they are in the cycle of three. For coin flips they need to remember nothing at all, because nothing in the past helps them guess.
In 1989 the physicists James Crutchfield and Karl Young turned this into a measure. Their trick is to group together every past that gives the same odds for what comes next, and call each group a causal state. In the stripes, every past that ends in black is one state and every past that ends in white is the other. The machine that hops between these states is the smallest thing that guesses the pattern as well as it can be guessed. The statistical complexity is how much information it takes to say which state the machine is in. Telling two equally likely states apart takes one yes or no question, called a bit. Three take about 1.6 bits, and a single state takes none.
This is a huge breakthrough. Simple, deterministic, low entropy systems like the stripes have low complexity, but so do high entropy, totally random ones. Complexity is what sits in the middle.
The problem is that it measures how much there is to remember rather than how organised it is, so a cycle of a thousand squares scores about 10 bits, far more than the middle pattern above, even though nothing in it ever changes. It also needs a long, steady record, which quietly assumes that watching one run for long enough tells you everything about the system. That holds for the stripes, but a cup of coffee only passes through its swirls once, and the systems we most want to measure, like a growing organism or an economy, never settle into a steady pattern at all.
Gershenson complexity
Most of the time, things with more entropy feel more complex. A rainforest, with thousands of species in every hectare, feels more complex than a field of wheat, a city more than a village, and a jazz solo more than a single held note. In each case there are far more ways the first could be arranged, so knowing the big picture tells you less about the details. But push entropy as high as it will go and the feeling disappears. The static on an untuned television and the gas in a balloon are as unpredictable as anything can be, and yet nobody would call them complex, because every part looks like every other and there’s nothing more to say about them than “random”.
In 2012 the complexity scientists Carlos Gershenson and Nelson Fernández turned this into a measure that is deceptively simple. Start with the information entropy of a system and divide it by the largest value it could ever take. Call the result I. It is 0 when every part is completely predictable and 1 when every part is as random as it can be. Their complexity is then
C = 4 × I × (1 − I)
where the 4 is only there so that the score tops out at 1.
It’s another huge leap forward. It’s simple, practical and entropy feels like the natural link to complexity. The problem is there are a number of cases it doesn’t work for. We go into these details here.
Fractal dimension
Imagine you’re asked how long a stretch of coastline is. The obvious way is to take a map and walk a ruler along the coast. The trouble is when you get a different answer depending on the size of the ruler.
In 1967 Benoit Mandelbrot wrote How long is the coast of Britain? and later coined the word fractal for shapes like this. The fractal dimension measures how quickly the length grows as the ruler shrinks. A straight line doesn’t grow at all and has a dimension of 1, a scribble so dense that it fills the page has a dimension of 2, and a coast sits in between, with the west coast of Britain at about 1.25 and the coast in the figure at about 1.26.
This is where it links back to the explainer on Complexity. A length is a macro state, a single number that sums up the micro state of every twist and turn. For most things that summary settles as you look closer, since a smooth curve looks straight once you zoom in far enough, and past that point the details can safely be averaged away. A fractal dimension above 1 says the opposite: however far you zoom in there’s more detail that changes the answer, so there’s no level at which you can stop and build a macro state that holds, unlike the levels of Simon’s nearly decomposable hierarchies. The English mathematician Lewis Fry Richardson met the same thing in the weather he spent years trying to forecast, with eddies at every size each feeding the next, and summed it up in a rhyme: “Big whirls have little whirls that feed on their velocity, and little whirls have lesser whirls and so on to viscosity.” Those whirls are just the kind of system hierarchical complexity misses (and Simon warned about), complex without being nested, and so hard to observe and understand.
The problem is that fractal dimension measures how much detail fills the space, not how organised that detail is.