Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton
This paper introduces a model system, a two-dimensional cellular automaton simulating the mixing of coffee and cream, to quantify the rise and fall of complexity in closed systems. It proposes an 'apparent complexity' measure based on Kolmogorov complexity of a coarse-grained approximation of the automaton's state.
Episodes
Chapters
01Abstract
Complexity in closed systems intuitively increases and then decreases, a pattern quantified by apparent complexity using a coffee and cream mixing automaton.
1:50Explained021 Introduction
This paper quantifies complexity in closed systems, proposing a model of coffee and cream mixing to demonstrate complexity's rise and fall as entropy increases.
1:47Explained032 Background
The text defines various entropy measures including Boltzmann, Gibbs, Shannon, and Kolmogorov complexity.
1:56Explained042 Background
Kolmogorov complexity, while uncomputable, is presented as a practical proxy for entropy due to its relation to computable compression, contrasting with complexity which is low for both simple and random objects.
1:37Explained052.1 Apparent Complexity
Apparent complexity is defined as the entropy of a smoothed version of an object, balancing simplicity with the challenge of defining the smoothing function.
1:54Explained062.2 Sophistication
Sophistication measures the non-random information in a string by considering models of the string and the information needed to specify it within those models.
1:40Explained072.3 Logical Depth
Logical depth quantifies complexity by the time taken by the shortest program to produce a string, representing computational effort rather than code size.
1:32Explained082.4 Light-Cone Complexity
Light-cone complexity measures the mutual information between a point's past and future light-cones in a causal system, assessing predictive information.
2:00Explained092.5 Synthesis
The four complexity measures—apparent complexity, sophistication, logical depth, and light-cone complexity—are related, with apparent complexity chosen for the experiment due to practical computability.
1:39Explained103 The Coffee Automaton
The coffee automaton simulates coffee and cream mixing using a 2D array, with two models: interacting and non-interacting.
1:29Explained113.1 Interacting Model
The interacting model swaps adjacent differing particles, reflecting physical constraints but posing theoretical challenges.
1:39Explained123.2 Non-Interacting Model
The non-interacting model has cream particles move independently, simplifying theoretical analysis through random walk dynamics.
1:19Explained13Abstract
The OSCR algorithm estimates string complexity by minimizing codebook and encoded string sizes, but a two-part code based on coarse-graining effectively approximates complexity by compressing the coarse-grained state.
1:40Explained14Coarse-Graining Experiment Method
Coarse-graining creates a new array by averaging nearby cells in the fine-grained array, and the complexity is estimated by compressing the thresholded coarse-grained array.
1:28Explained15Results and Analysis
Both interacting and non-interacting models exhibit a complexity pattern of increasing then decreasing, with entropy generally increasing, and visualizations show the fine-grained state becoming more complicated while the coarse-grained state follows a more intuitive pattern.
1:50Explained16Adjusted Coarse-Graining Experiment Method
The adjusted coarse-graining algorithm uses more thresholds and allows independent pixel adjustments to minimize artifacts introduced by simple thresholding, while a majority algorithm is used to approximate optimal adjustments.
1:45Explained17Adjustment Algorithm
An approximation algorithm using a majority rule adjusts coarse-grained arrays to reduce artifacts by flattening fluctuating border rows without eliminating actual complexity.
1:27Explained18Figures
Figures illustrate compression program comparisons, entropy and complexity maximums relative to automaton size, and the effect of noise and thresholding on coarse-grained arrays.
1:31Explained19Adjusted Coarse-Graining Results
The adjusted coarse-graining metric produces a flattened complexity curve for the non-interacting automaton, suggesting that initial complexity estimates were artifacts of thresholding.
1:31Explained20Figure 11
This figure visualizes the state of the interacting automaton over time, showing the fine-grained state, the original coarse-grained state, and the adjusted coarse-grained state.
1:22Explained21Figure 12
This figure visualizes the state of the non-interacting automaton over time, with darker coarse-grained images due to a larger number of thresholds.
1:13Explained22Conclusions and Further Work
Coarse-graining provides an intuitive complexity estimate, but the OSCR approach and light cone metrics offer promising alternatives that avoid human intuition and artifacts, with further theoretical work needed to establish lower bounds on complexity.
1:47Explained23Bad Squares Analysis
By using a Chernoff bound and choosing a sufficiently large coarse-grain size, the probability of any L x L square deviating from its expected value is shown to be very low, implying that the coarse-grained image is correctable with high probability.
1:58Explained24References
This section lists the academic papers and books cited in the document.
1:41Explained