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

Title

This document is titled "Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton" by Scott Aaronson, Sean M. Carroll, and Lauren Ouellette.

Abstract

This abstract introduces a model system, a two-dimensional cellular automaton simulating coffee and cream mixing, to quantify the rise and fall of complexity in closed systems, defining a complexity measure as the Kolmogorov complexity of a coarse-grained approximation of the system's state.

Introduction

The introduction uses the analogy of coffee and cream mixing to explain the concept of increasing entropy and intuitively decreasing complexity in closed systems over time, motivating the paper's aim to formally define and measure complexity.

Introduction (cont.)

The text further illustrates the rise and fall of complexity using the universe as an example, from the Big Bang to heat death, and states the paper's goal to explore a principle of complexity through formal definition and numerical experiments.

Background on Entropy Measures

This section discusses various definitions of entropy, including Boltzmann, Gibbs, Shannon, and Kolmogorov complexity, laying the groundwork for understanding complexity measures by first defining related concepts of disorder.

Kolmogorov Complexity and its Relation to Entropy

This section clarifies the equivalence between Gibbs and Shannon entropy, introduces Kolmogorov complexity as the length of the shortest program to output a string, and notes that while Kolmogorov complexity is uncomputable, it serves as a valuable theoretical concept for measuring information content and lack of regularity.

Apparent Complexity

Apparent complexity is defined as the entropy of a smoothed or 'denoised' version of an object, aiming to capture 'interesting' information while discarding 'incidental' or 'random' details, offering computational advantages despite potential arbitrariness in the smoothing function.

Sophistication

Sophistication is introduced as a measure that generalizes Kolmogorov complexity to capture non-random information, defined by finding a 'model' for a string that balances the complexity of describing the model with the complexity of describing the string within that model.

Logical Depth

Logical depth, a third complexity notion, measures the time taken by the shortest program to output a string, suggesting that complex strings can be generated by short programs but require significant computational effort, distinguishing 'interesting code' from 'boring data'.

Light-Cone Complexity

Light-cone complexity is defined as the mutual information between a system's past and future light-cones, aiming to quantify how much of a system's future can be predicted from its past, offering an operational meaning related to causal structure.

Synthesis of Complexity Measures

This section synthesizes the discussed complexity measures, relating apparent complexity to resource-bounded sophistication, and noting the connections between coarse sophistication, logical depth, and a looser relationship between light-cone complexity and apparent complexity.

The Coffee Automaton Model

The paper introduces a two-dimensional stochastic cellular automaton as a model system, where cells represent either coffee (0) or cream (1), starting with a separated state and evolving over time.

Interacting and Non-Interacting Models

Two models of the coffee automaton are described: the 'interacting model' where only one particle occupies a cell and positions are swapped, and the 'non-interacting model' where multiple cream particles can occupy a cell and move independently.

Approximating Apparent Complexity

This section discusses the challenge of approximating uncomputable complexity measures like Kolmogorov complexity and sophistication, and details the exploration of the Optimal Symbol Compression Ratio (OSCR) algorithm and a coarse-graining approach.

Coarse-Graining Method for Complexity Approximation

The paper details a coarse-graining method to approximate complexity by averaging nearby cells in the automaton's state and then compressing the resulting smoothed representation, using compressed file size as a proxy for Kolmogorov complexity.

Coarse-Graining Experiment Results

Results from the coarse-graining experiment show both interacting and non-interacting models exhibit an increase and then decrease in complexity, consistent with predictions, while entropy consistently increases.

Analysis of Complexity Trends

The analysis of complexity trends reveals that maximum complexity increases linearly with automaton size for both models, while the time to reach maximum complexity increases quadratically, suggesting complexity develops along a single dimension.

Adjusted Coarse-Graining Experiment

An adjusted coarse-graining method is introduced with more thresholds and a majority-based adjustment to reduce artifacts, aiming to provide a more accurate complexity measure by minimizing fluctuations at threshold boundaries.

Adjusted Coarse-Graining Results

The adjusted coarse-graining metric shows a noisier but similarly shaped complexity curve for the interacting automaton, while significantly flattening the curve for the non-interacting automaton, suggesting the latter model never becomes truly complex.

Interacting Automaton Visualization

This section presents a visualization of the interacting automaton's state over time, showing the fine-grained array for entropy estimation and the coarse-grained array for complexity estimation, illustrating the complexity maximum.

Non-Interacting Automaton Visualization

This section provides a visualization of the non-interacting automaton's state over time, highlighting the coarse-grained images which appear darker due to the increased number of thresholds used in the adjusted coarse-graining metric.

Conclusions and Further Work

The paper concludes that coarse-graining approaches like apparent complexity effectively estimate complexity based on intuition, but suggests further work on metrics like OSCR and light-cone complexity for greater independence from human perception and theoretical rigor.

Acknowledgments

The authors express their gratitude to several individuals for their helpful discussions and contributions to the research.

Appendix: The Non-Interacting Case

This appendix provides a theoretical analysis of the non-interacting coffee automaton, demonstrating that its complexity remains low due to predictable particle distribution, even with periodic boundary conditions.

References

This section lists the academic papers and resources cited throughout the document, providing a bibliography for the research presented.