Event Type


The Coffee Automaton: Quantifying the Rise and Fall of Complexity in Closed Systems

Wed, 18/07/201214:00
Ross bld. room 201, Givat Ram Campus
Prof. Scott Aaronson, MIT


In contrast to entropy, which increases monotonically, the "complexity" or "interestingness" of closed systems seems intuitively to increase and then decrease: for example, our universe lacked complex structures at the Big Bang and will also lack them after it reaches thermal equilibrium. I'll discuss an initial attempt to quantify this pattern. As a model system, we use a simple, two-dimensional cellular automaton that simulates the mixing of two liquids ("coffee" and "cream"). A plausible complexity measure is then the Kolmogorov complexity of a coarse-grained approximation of the automaton's state. We study this complexity measure, and show analytically that it never becomes large when the liquid particles are non-interacting. By contrast, when the particles do interact, we give numerical evidence that the complexity reaches as a maximum comparable to the "coffee cup's" horizontal dimension. We raise the problem to prove this behavior analytically. 
Joint work with Lauren Ouellette and Sean Carroll.