Event Type

Year

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

aarsmall.gif
Date: 
Wed, 18/07/201214:00
Location: 
Ross bld. room 201, Givat Ram Campus
Lecturer: 
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.