LLM + RoboticsUnit 1 · The foundations · Day 06

The First Law of Complexodynamics

Entropy only goes up. "Interestingness" rises and then falls. Why, and can you even define it? A blog post that turns a cosmologist's question into a computer-science problem.

AuthorScott Aaronson

Year / venue2011 · blog post (Shtetl-Optimized)

Core ideaResource-bounded sophistication ("complextropy")

Study time1–2 h

Original: scottaaronson.blog · Code, notebook and exercises: 30u30 Day 6

Start here (no maths needed)

Mess (entropy) only ever goes up, but "interesting-ness" goes up and then back down, and this blog post asks how to measure that.

Think of it like this

Pour milk into a cup of coffee and don't stir. At first it's simple: milk on top, coffee below. At the end it's simple again: plain light-brown coffee. In the middle you get beautiful swirls and tendrils. That middle moment is the "interesting" one, even though the mess keeps increasing the whole time. The question is how a computer could put a number on "interesting".

How it works

One way to score something is "how hard is it to describe?" A random jumble is very hard to describe.
But a random jumble is not interesting. It is just noise. So that score measures mess, not interest.
A better score asks only for the size of the pattern part, ignoring the random part.
Aaronson adds one more rule: the describing has to be done quickly, not with unlimited computer time.
He guesses this score will be low at the start, high in the middle and low at the end. Nobody has proved it yet.

Why robots care

A robot's camera sees a lot of random detail, like flickering leaves or carpet patterns. A good robot learns to ignore that random part and keep the patterns that matter, like where the table edge is. That is the same "pattern vs. noise" split this post is about.

Try it

Draw three squares on paper: one all white, one with a careful swirl pattern, and one filled with random dots. Ask a friend which is hardest to describe in words, and which is most interesting. They usually aren't the same picture.
In the demo further down, slide the Step t slider to the right. A very short rule makes a pattern that looks random. The compressed-size line shows a zip-style program needing more and more bits. The log₂ t line shows how little the real description grows.

Words to know

Entropy: A measure of how mixed-up or random something is.
Kolmogorov complexity: The length of the shortest computer program that prints something.
Sophistication: How big just the pattern part of a description is.
Conjecture: A guess that someone believes is true but hasn't proved.

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings and the "Why it matters for robotics" box, and come back for the rest later.

1. Summary

TL;DR

At a 2011 FQXi conference on time, Sean Carroll asked why the complexity of a closed system seems to rise and then fall while entropy just rises. Pour milk into coffee: separated layers are simple, the fully mixed cup is simple, the swirling tendrils in between are complex. Aaronson's answer is a definition and a conjecture. Kolmogorov complexity measures randomness, not interest. Sophistication measures only the non-random structure, but for simple physical processes it stays small. Add computational resource limits to both halves and you get "complextropy", which he conjectures follows the rise-and-fall curve. He also proposed testing it on a pixel coffee cup, which became Day 07.

Kolmogorov complexity K(x): length of the shortest program that prints x. High for random strings, so it tracks entropy, not complexity.
Sophistication: the size of the shortest description of a set S in which x is a typical, random-looking member. Low for simple and for random strings.
The catch: for any process with a short rule, the state at time t can be described by the rule, the start state and t. So without resource bounds, both measures stay tiny, around log t.
Complextropy: sophistication where both the sampler for S and the reconstructor for x must run fast.
Status: an open conjecture. The post is explicit that it has no proof.

2. The core idea

Three quantities for an n-bit string x:

K(x)       = min { |p| : program p prints x }

Soph(x)    = min { K(S) : x ∈ S  and  K(x | S) ≥ log₂|S| − c }

Complextropy(x) ≈ Soph(x), but every program involved must run in
                  limited time (Aaronson's example bound: n·log n)

K(x): all the information in x, structure and noise together. It's uncomputable, but a compressor like gzip gives an upper bound.
S: a "model" for x, a set of strings that share its structure. Saying "x is in S" captures the meaningful part.
K(x | S) ≥ log₂|S| − c: once you know S, x needs almost the full log₂|S| bits to pick out. In other words, x looks random inside S, so S has captured all the pattern.
Soph(x): the cost of the smallest such model. All zeros: S = {x}, tiny. A coin-flip string: S = all n-bit strings, also tiny. Only strings that are neither simple nor random score high.

This is the two-part code of Day 05 again. K(S) is the model part, log₂|S| is the noise part. Sophistication asks how big the model part has to be.

3. Deep dive

Why the definitions need a time limit

Suppose a system follows a short, deterministic rule from a simple start. Its state after t steps can be printed by a tiny program: "start here, apply the rule t times". That program is a fixed size plus about log₂ t bits for t. So K(state) grows only logarithmically, though the state may look completely random. Sophistication is stuck the same way, and the post shows a counting argument extends this to probabilistic rules. The resolution is that "looks random" really means "looks random to any efficient procedure". So Aaronson puts time bounds on both the program that samples from S and the program that recovers x. Remove the first and complextropy stays near log t. Remove the second and he expects it to keep rising instead of falling.

Interactive: a tiny rule that a compressor can't see through

Wolfram's Rule 30, started from one black cell. Left: rows 0 to t. Right: LZ78-compressed size of row t (a stand-in for gzip) against log₂ t, the only part of the true shortest description that grows. The rule itself is a fixed, small number of bits.

Step t:

Row length (bits)

–

LZ78 size (bits)

–

log₂ t (bits)

–

The compressor's estimate grows roughly in proportion to the row, like a random string. The true Kolmogorov complexity is at most the size of the Rule 30 program plus log₂ t. A time-limited observer, like the compressor, sees entropy. An unlimited one sees almost nothing. That gap is why Aaronson's definition is built around resource bounds.

The rival ideas

Logical depth (Charles Bennett): how long the shortest program takes to run. Deep objects took a lot of computation to make. Bennett and Sean Carroll both join the comment thread, which is worth skimming.
Coarse-grained entropy: blur the state, then compress it. Simple and computable, but the blur is a human choice. This "apparent complexity" is what Day 07 actually measures.
Effective complexity (Gell-Mann and others) is a close relative of sophistication. Nobody has a measure that is both principled and easy to compute.

What to take from it

The post doesn't prove anything. Its value is turning a vague question into a precise conjecture, and the move it makes, separating structure from noise with a two-part code under limited computation, recurs across this course. Ilya Sutskever has often described learning as compression. Read this post as the "what does structure even mean" side of that bet.

4. Why it matters for robotics

Plainly: the link is conceptual. No robot controller computes complextropy. The ideas below are ways of thinking, not tools.
Structure vs noise in sensor data. A camera feed of a sunlit leafy scene has high entropy but little task-relevant structure. Good representations keep the "model" part and discard the noise part, which is what sophistication formalises.
Bounded observers. A robot is a time-limited observer. What counts as predictable for it depends on its compute, the same point the resource bounds make. Hence the push for fast learned models (Module 04).
Where the interesting data lives. In manipulation, the informative moments are the in-between ones: contact, slipping, partial mixing. Curriculum and data-collection strategies that seek "neither trivial nor random" states echo this curve.

5. How to study it

Read the post (about 30 min). Then skim the comments for the logical-depth discussion.
Write the three definitions from memory and give an example string that scores low on each.
In the 30u30 Day 6 folder, run train_minimal.py and read implementation.py to see gzip-based estimates on a mixing simulation.
Do the exercises: gzip as a complexity proxy, coffee mixing, multi-scale analysis, two-part codes, and a comparison of measures.
Stretch: compress Rule 30 rows with gzip, bzip2 and xz. Do any of them beat the LZ78 curve in the demo by much?

6. Self-check

Why is Kolmogorov complexity a measure of entropy, not interestingness?

It is maximal for random strings. A coin-flip sequence has huge K but no interesting structure.

Why does a uniformly random string have low sophistication?

Take S to be all n-bit strings. Describing S is cheap, and the string is a typical member of it.

Why can't unbounded K or sophistication capture the coffee cup's rise and fall?

The state at time t is described by the start state, the rule and t, which is a constant plus about log t bits. Neither measure can grow faster than that.

What are the two places Aaronson adds time limits?

On the program that samples from the model set S, and on the program that reconstructs x given samples from S.

Is the "First Law of Complexodynamics" a theorem?

No. It's a conjecture. The post says plainly that Aaronson doesn't know how to prove it.

7. Further reading

The original post and its comment thread
30u30 Day 6: implementation, notebook, cheatsheet, exercises
Next: Day 07, The Coffee Automaton