The First Law of Complexodynamics

Host: Let's dive into a fascinating puzzle about the flow of time and how the universe evolves. The author of our text, a quantum complexity blogger, recently attended a unique physics conference on a cruise ship dedicated to the nature of time. Guest: A physics conference on a cruise ship sounds like a pretty captive audience for debating time. Host: It certainly kept attendees from sneaking away. During the opening talk, physicist Sean Carroll posed a really beautiful question about a strange contrast between entropy and complexity. Guest: I know entropy generally means things get more disordered as time passes, but aren't entropy and complexity basically the same thing? Host: That's exactly the distinction Carroll wanted to highlight. The Second Law of Thermodynamics dictates that entropy always increases, meaning closed systems inevitably become more random and generic. Guest: So if entropy is always going up, what is complexity doing? Host: Complexity, or how interesting a physical system is, actually tends to increase with time, hit a maximum peak, and then decrease. While isolated systems get steadily more entropic, they don't get continuously more complicated. Guest: That's really counterintuitive, so why would interestingness go up and then eventually come back down? Host: That's the core mystery the author wants to solve using a mathematical concept called Kolmogorov complexity. We already accept that the universe started with low entropy and naturally drifts toward generic states, but this temporary peak in complexity is a separate puzzle we're about to explore.

Host: It turns out there is a fascinating difference between how messy things get and how complicated they become. If you picture a series of photos showing milk mixing into a drink, the overall disorder, or entropy, steadily increases from the first frame to the last. Guest: But the visual complexity doesn't just go straight up, does it? The middle picture, with all those swirling tendrils of milk, seems way more intricate than the fully mixed drink at the end. Host: Exactly, the complexity actually peaks in the middle, and the exact same thing is true for the entire universe. Right after the Big Bang, the cosmos was basically just a simple, low-entropy soup of high-energy particles. Guest: So it started out really simple. What happens at the very end of the universe's timeline, then? Host: A googol years from now, long after the last black holes have sputtered away in bursts of Hawking radiation, the universe goes back to being simple. It'll basically just be a high-entropy soup of low-energy particles. Guest: Oh, so it starts as a highly concentrated soup and ends as a totally watered-down, boring soup. Where does that leave us right now? Host: We are in that beautiful middle stage where complexity peaks. It's the cosmic equivalent of those milk tendrils, which is why the universe currently contains interesting structures like galaxies, brains, and even hot-dog-shaped novelty vehicles. Guest: That makes perfect sense. The universe's entropy just keeps rising, but all this amazing complexity is just a temporary phase in between.

Host: Let's look at how we can actually pin down and mathematically measure what makes a system complex. We are trying to answer a really provocative question: is there a law of "complexodynamics" that explains why things get complicated over time? Guest: Are we trying to explain why a system starts out simple, gets highly complex in the middle, and then ends up simple again? Host: Exactly, and the beginning and end are actually the easy parts to explain. At the very start, the system's entropy is close to zero, which naturally puts a strict ceiling on its complexity. Guest: And what happens at the end of the timeline to make it simple again? Host: At late times, the system reaches equilibrium, meaning it just becomes a uniform distribution over all possible states. We essentially define that perfectly mixed, uniform blur as being simple. Guest: So during the intermediate times, those boundaries are gone and complexity is free to grow. How do we prove that it actually gets large? Host: That is our twofold challenge: we have to formally define what "complexity" is, and then prove it spikes in the middle. The author conjectures we can solve this using a concept from computer science called Kolmogorov complexity. Guest: I don't think I've heard of that one. What does Kolmogorov complexity actually measure? Host: It looks at a string of data and asks for the length of the shortest possible computer program that can generate it. The author plans to use a more advanced version of this idea, called "sophistication," to finally capture what's happening in that messy middle phase.

Host: We are looking at how to measure chaos and information by tying the idea of entropy to computer code. As a first step, we want to use Kolmogorov complexity, which is the length of the shortest computer program that can describe a system, as our stand-in for entropy. Guest: That sounds like an elegant way to measure it, but does it actually work for physical systems, like billiard balls bouncing around on a table? Host: Visually those systems look like they are getting more chaotic, but mathematically we hit a snag if the system follows perfectly predictable, deterministic laws. To describe a deterministic system after a certain number of time steps, you only need to feed a computer two things: the starting setup, and the total number of steps. Guest: So I just tell the computer the initial state, say to run it for a thousand steps, and it figures out the exact final state? Host: Exactly, and that creates a paradox. The starting setup takes a fixed amount of data, and the number of steps takes logarithmic space, meaning writing a huge number like one million in binary takes only about twenty bits. Because the program stays so short, our calculated entropy barely grows at all, which contradicts the massive increase we intuitively expect over time. Guest: Because the instruction manual is so brief, the complexity appears artificially low. How do we fix our math so it matches reality? Host: The text offers two main workarounds, the first being to look at probabilistic systems instead of perfectly predictable ones. If random things happen along the way, you need a longer program to describe the exact outcome, and the complexity shoots up at the faster rate we expect. Guest: That makes total sense. What is the second workaround? Host: The second option is to use what is called resource-bounded Kolmogorov complexity. We still look for the shortest program, but we add a strict rule that the program must output the answer in a short amount of time. Guest: Oh, I see. Even if the shortcut command to run for a million steps is extremely short to type, it might take way too much time for the computer to actually calculate the result. Host: You nailed it. By banning those short but incredibly slow programs, we force the shortest allowed program to be much longer, and just like that, our calculated complexity grows at a realistic rate.

Host: Now that we've covered basic entropy, let's look at what makes a sequence of data genuinely interesting, a concept the author calls complextropy. Back in the 1970s, Andrey Kolmogorov realized that a purely random sequence of data is actually one of the least interesting things imaginable. Guest: That feels contradictory to me, because wouldn't a completely random sequence require a very long and complex computer program to generate? Host: It does require a long program to print that exact sequence, which means it has high Kolmogorov complexity. However, it completely lacks structure, because you can summarize everything meaningful about it just by saying that it is a random string. Guest: That makes sense, but how do we mathematically separate that structural richness from pure randomness? Host: We use a metric called sophistication. Instead of looking for the shortest program to print the exact string, we find the shortest program that describes a larger set of strings, where our target string is just a generic member of that set. Guest: Can you walk me through how that applies to our completely random string? Host: Sure, for a completely random string, the set it belongs to is just the group of all possible strings of that length. Telling a computer to generate the set of all possible strings takes almost zero code, so the random string has very low sophistication. Guest: And what about a highly predictable sequence, like a simple repeating pattern? Host: That also has low sophistication, because its set only needs to contain that one specific, easily described pattern. Because both extremes are so simple to group, it actually raised a major mathematical question about whether highly sophisticated strings exist at all. Guest: Did they ever find any strings that actually have high sophistication? Host: Yes, they did. In the early 1980s, a mathematician named Alexander Shen used a highly complicated proof to confirm that these truly sophisticated, structurally rich strings do in fact exist.

Host: Let us explore how limits on computing power might finally help us measure the true complexity of a changing system. But first, we have to look at why our previous best idea, a concept called sophistication, does not quite work for a classic example like milk mixing into coffee. Guest: Wait, I thought sophistication was exactly what we wanted? It is supposed to be low for simple things, low for completely random things, and high for that weird middle ground where the coffee and milk are actively swirling. Host: It seems perfect at first glance, but it falls into a major trap when dealing with systems that change over time. If the system is strictly deterministic, there is a massive shortcut to describing its current state. Guest: What kind of shortcut? Host: Instead of describing that incredibly complicated swirling pattern drop by drop, you can just tell a system to start with black coffee and white milk, apply a specific transition rule, and run it for exactly t time steps. Guest: Oh, I see. Since the starting point and the rules are simple, you only really need to specify the time, which is just the number t. Host: Exactly. And writing down a number t only takes about the logarithm of t bits of data. Because of this shortcut, the sophistication never actually grows large for that middle state, since the description is artificially capped by that tiny amount of information. Guest: But what if the mixing process is not strictly deterministic? What if the particles bounce around with some randomness? Host: Unfortunately, the same loophole applies there too. You can use that exact same short description to specify the entire set of possible states at that specific time t. Guest: So because the overall set of possibilities is easy to describe, any generic swirling pattern inside that set also gets a falsely low complexity score? Host: Spot on. By relying purely on the absolute shortest mathematical description, the formula completely ignores how unbelievably hard it would be to actually calculate that middle state in practice.

Host: Let's take a quick detour to look at how scientists handle seemingly impossible news. The author adds an unrelated postscript here, bringing up a headline about neutrinos traveling faster than light. Guest: Wait, faster than light? I thought Einstein proved nothing could break that universal speed limit. Host: He did, which is exactly why a 2011 experiment that seemed to track faster-than-light neutrinos caused such a massive uproar. To demonstrate the proper reaction to this kind of shock, the author points us to a comic strip from XKCD. Guest: How did the comic react to the news? Host: With extreme skepticism, basically joking that if you have to choose between a loose cable in your testing equipment or the fundamental laws of physics being broken, you should bet on the loose cable. The author says this perfectly captured what he was trying to do during the "Deolalikar affair." Guest: The Deolalikar affair? That sounds like a Cold War spy scandal. Host: It was actually an academic drama in 2010, when a researcher named Vinay Deolalikar claimed to have solved the biggest open problem in theoretical computer science. Guest: Oh, so the author was trying to express that same level of baseline doubt about the math proof? Host: Exactly. He was highly skeptical of the math claim at the time, but he humbly admits the comic conveyed that necessary scientific skepticism much better than he did.