Literature
Display
← All papers

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

Scott Aaronson · Sean M. Carroll · Lauren Ouellette

Preprint posted · arXiv (preprint) ↗

Learning theory5 min text · CondensedOriginal paper ↗
Contents

At a glance

Can a closed system become more structured while its entropy increases? The coffee automaton separates fine-grained disorder from the descriptive complexity of a smoothed state. Simulations support a rise and fall of apparent complexity for interacting particles. An apparent peak for independent particles disappears after correcting threshold artifacts; the appendix explains why their corrected complexity stays small. This is evidence about a particular model and measurement, not a proved universal law of complexity.

1 Introduction

Initially separated coffee and cream have a simple large-scale description, as does the final homogeneous mixture. Intermediate tendrils seem harder to describe. The paper asks how to measure this distinction from entropy and tests it in a stochastic cellular automaton, motivated by the broader appearance and disappearance of structure in closed systems.

2 Background

Boltzmann entropy counts microstates compatible with a chosen macrostate; Gibbs/Shannon entropy describes a probability distribution. Kolmogorov complexity measures the shortest program describing an individual string. These measures are related under suitable assumptions but all can be large for randomness, so none alone captures meaningful structure. Actual Kolmogorov complexity is uncomputable; compressed file size supplies only a computable upper bound.

Equations 1–3
SBoltzmann​(xa):=kB​log⁡WA,S_{\mathrm{Boltzmann}}(x_{a}):=k_{B}\log W_{A}, (1)
SGibbs[ρ]:=−∑xρ(x)logρ(x).S_{\mathrm{Gibbs}}[\rho]:=-\sum_{x}\rho(x)\log\rho(x). (2)
H(D):=−∑xpxlogpx.H(D):=-\sum_{x}p_{x}\log p_{x}. (3)

2.1 Apparent Complexity

Apparent complexity applies an entropy or description-length measure after smoothing away incidental detail. Blurring an image can make both uniform and noisy states simple while retaining intermediate structures. The advantage is a tractable, intuitive experiment; the limitation is the chosen smoothing rule. Spatial locality motivates the rule, but does not make it unique.

2.2 Sophistication

Sophistication describes the simplest model set in which a string is a typical member, separating model structure from residual randomness. The definition uses a tolerance for incompressibility; small changes in that tolerance can substantially change the value. Coarse sophistication trades tolerance against model length instead. Both are uncomputable and harder to approximate reliably than apparent complexity. [6, 8, 10, 13]

2.3 Logical Depth

Logical depth measures the computation needed to produce a string from a near-shortest description. Random strings can be shallow because printing them is quick, whereas structured strings may require long computation. The parameter controlling near-optimality and the lack of efficient approximations complicate direct measurement. [2]

2.4 Light-Cone Complexity

Light-cone complexity uses information shared between a point’s causal past and future. It measures predictive structure in an entire space-time history rather than solely the current state. Algorithmic-information variants can be approximated with compression, but introduce different sampling and estimation problems. [12]

Equations 4–8
F⁡(x,t)\displaystyle F\left(x,t\right) ={(y,u):u>t,|x−y|≤u−t},\displaystyle=\left\{\left(y,u\right):u>t,~~\left|x-y\right|\leq u-t\right\}, (4)
P⁡(x,t)\displaystyle P\left(x,t\right) ={(y,u):u<t,|x−y|≤t−u}.\displaystyle=\left\{\left(y,u\right):u<t,~~\left|x-y\right|\leq t-u\right\}. (5)
LCC(a)\displaystyle\operatorname*{LCC}\left(a\right) =I⁡(VP⁡(a):VF⁡(a))\displaystyle=I\left(V_{P\left(a\right)}:V_{F\left(a\right)}\right) (6)
=H⁡(VP⁡(a))+H⁡(VF⁡(a))−H⁡(VP⁡(a),VF⁡(a)).\displaystyle=H\left(V_{P\left(a\right)}\right)+H\left(V_{F\left(a\right)}\right)-H\left(V_{P\left(a\right)},V_{F\left(a\right)}\right). (7)
K⁡(VPt​(a):VFt​(a))=K⁡(VPt​(a))+K⁡(VFt​(a))−K⁡(VPt​(a),VFt​(a)),K\left(V_{P_{t}\left(a\right)}:V_{F_{t}\left(a\right)}\right)=K\left(V_{P_{t}\left(a\right)}\right)+K\left(V_{F_{t}\left(a\right)}\right)-K\left(V_{P_{t}\left(a\right)},V_{F_{t}\left(a\right)}\right), (8)

2.5 Synthesis

Apparent complexity can be viewed as restricting the model search in sophistication to a chosen smoothing function. Coarse sophistication is related to a Busy Beaver version of logical depth, while light-cone information may track contingent structures. These links do not make the notions interchangeable or establish an upper/lower ordering between ordinary sophistication and apparent complexity. The experiments use smoothing plus gzip because the alternatives lack an efficient estimator. [1]

Equations 9–10
Sf,x:={y:f⁡(y)=f⁡(x)}.S_{f,x}:=\left\{y:f\left(y\right)=f\left(x\right)\right\}. (9)
|csoph(x)−depthB​B(x)|=O⁡(log⁡n).\left|\operatorname*{csoph}\left(x\right)-\operatorname*{depth}\nolimits_{BB}\left(x\right)\right|=O\left(\log n\right). (10)

3 The Coffee Automaton

A square grid begins half cream and half coffee. Two transition rules distinguish exclusion-based interactions from independent diffusion; these rules define the system being studied rather than a full fluid simulation.

3.1 Interacting Model

One particle occupies each cell. Each update chooses adjacent, different particles and swaps them. Occupancy exclusion couples their movements and can generate correlated spatial structures. This simple interaction also makes the model harder to analyze.

3.2 Non-Interacting Model

Any number of cream particles may occupy a cell; coffee is only background. At each step every cream particle takes an independent random walk. Independence makes expectations and concentration bounds tractable, providing a control against which measurement artifacts can be recognized.

4 Approximating Apparent Complexity

An implementation of OSCR produced noisy estimates and did not capture the grid’s two-dimensional structure well. The authors instead compress smoothed arrays to estimate apparent complexity and compress original arrays to estimate disorder. An attempted two-part encoding of the residual introduced its own artifacts, so these two estimates are measured separately. Generic compression remains an approximation, not an oracle for algorithmic complexity. [5, 11]

5 Coarse-Graining Experiment

The first experiment uses a spatial moving average and a three-level threshold to distinguish coffee-rich, mixed and cream-rich regions.

5.1 Method

Average each cell’s neighborhood over a square of side g, threshold the resulting values into three levels, then measure the compressed file size. The unsmoothed array’s compressed size supplies the entropy proxy. Grain size is chosen experimentally; the measurement is therefore conditional on that resolution and encoding.

Fine-grained and coarse-grained 5 by 5 arrays. Nine shaded cells in the left array average to the shaded 0.6 in the right array.
Figure 1: Illustration of the construction of the coarse-grained array, using an example grain size of 33. The values of the shaded cells at left are averaged to produce the value of the shaded cell at right.

5.2 Results and Analysis

Both models initially appear to show increasing disorder and a rise then fall in apparent complexity. Across tested sizes, maximum disorder scales approximately with grid area; peak complexity scales with side length, and time to peak approximately quadratically. Alternative compressors give qualitatively similar curves. These first results are provisional: the next experiment identifies artificial complexity created by threshold crossings.

Refer to captionRefer to caption

Figure 2: The estimated entropy and complexity of an automaton using the coarse-graining metric. Results for the interacting model are shown at left, and results for the non-interacting model are at right.
𝐭=𝟎\mathbf{t=0} 𝐭=𝟖×𝟏𝟎𝟔\mathbf{t=8\times 10^{6}} 𝐭=𝟐×𝟏𝟎𝟕\mathbf{t=2\times 10^{7}}
Refer to caption Refer to caption Refer to caption
Refer to caption Refer to caption Refer to caption
Figure 3: Visualization of the state of the interacting automaton of size 100100 over time. The top row of images is the fine-grained array, used to estimate entropy. The bottom row is the coarse-grained array, used to estimate complexity. From left to right, the images represent the automaton state at the beginning of the simulation, at the complexity maximum, and at the end of the simulation.
𝐭=𝟎\mathbf{t=0} 𝐭=𝟓𝟎𝟎𝟎\mathbf{t=5000} 𝐭=𝟏𝟎𝟎𝟎𝟎\mathbf{t=10000}
Refer to caption Refer to caption Refer to caption
Refer to caption Refer to caption Refer to caption
Figure 4: Visualization of the state of the non-interacting automaton of size 100100 over time.

Refer to caption

Figure 5: Coarse-grained complexity estimates for a single simulation of the interacting automaton, using multiple file compression programs.

Refer to captionRefer to caption

Figure 6: Graphs of automaton size versus entropy maximum value. Quadratic curve fits are shown, with r2r^{2} values of 0.99990.9999 for both the interacting and non-interacting automaton.

Refer to captionRefer to caption

Figure 7: Graphs of automaton size versus complexity maximum value. Linear curve fits are shown, with r2r^{2} values of 0.97980.9798 for the interacting automaton and 0.97290.9729 for the non-interacting automaton.

Refer to captionRefer to caption

Figure 8: Graphs of automaton size versus time to complexity maximum. Quadratic curve fits are shown, with r2r^{2} values of 0.9878 for the interacting automaton and 0.9927 for the non-interacting automaton.

6 Adujsted Coarse-Graining Experiment

The revised estimator tests whether small fluctuations around threshold boundaries masquerade as meaningful spatial structure.

6.1 Method

Use seven levels and allow each pixel to shift by one level to reduce artificial boundary noise. Exact minimization would require an exponential search. The implemented approximation moves a cell to its row’s majority level when they differ by at most one. It is motivated by the initial horizontal layering and may affect structures differently in other geometries.

Refer to captionRefer to caption

Figure 9: A coarse-grained array consisting of a smooth gradient from 00 to 11 is shown at left. At right is the same array after a small amount of simulated noise has been added and the values have been thresholded.

6.2 Results and Analysis

The interacting model retains a rise and fall in adjusted complexity; the independent model’s apparent peak largely disappears. Row symmetry determines the independent model’s expected density, while concentration bounds keep sufficiently large neighborhoods near that expectation. Its original peak was therefore attributable to threshold artifacts. For interacting particles the remaining peak is numerical evidence; no matching complexity lower bound is proved.

Refer to captionRefer to caption

Figure 10: The estimated entropy and complexity of an automaton using the adjusted coarse-graining metric.
𝐭=𝟎\mathbf{t=0} 𝐭=1.4×𝟏𝟎𝟕\mathbf{t=1.4\times 10^{7}} 𝐭=𝟒×𝟏𝟎𝟕\mathbf{t=4\times 10^{7}}
Refer to caption Refer to caption Refer to caption
Refer to caption Refer to caption Refer to caption
Refer to caption Refer to caption Refer to caption
Figure 11: Visualization of the state of the interacting automaton of size 100100 over time. The rows of images represent the fine-grained state, the original coarse-grained state, and the coarse-grained state after adjustment, respectively.
𝐭=𝟎\mathbf{t=0} 𝐭=𝟏𝟎𝟎𝟎𝟎\mathbf{t=10000} 𝐭=𝟐𝟎𝟎𝟎𝟎\mathbf{t=20000}
Refer to caption Refer to caption Refer to caption
Refer to caption Refer to caption Refer to caption
Refer to caption Refer to caption Refer to caption
Figure 12: Visualization of the state of the non-interacting automaton of size 100100 over time. Note that the coarse-grained images are darker than for the previous coarse-graining metric, because a larger number of thresholds were used.

7 Conclusions and Further Work

Coarse-graining gives a useful but observer-dependent proxy. Alternative estimators, including light-cone information, could test robustness. A compressor establishes only an upper bound on description length, so simulations cannot prove that an intermediate state has intrinsically high algorithmic complexity. A rigorous lower bound for the interacting model remains open.

8 Acknowledgments

The authors acknowledge discussions with Alex Arkhipov, Charles Bennett, Ian Durham, Dietrich Leibfried, Aldo Pacchiano and Luca Trevisan.

9 Appendix: The Non-Interacting Case

For independent particles on a periodic grid, every cell’s expected occupancy stays at most one and depends only on its row. A Chernoff bound controls deviations of the number of particles in a square neighborhood; a union bound covers all neighborhoods at a fixed time. With grain size sufficiently larger than a constant times √log n, a one-level correction yields the row-symmetric expected pattern with high probability. Its description needs only the grid size, time and a fixed program, giving logarithmic rather than extensive complexity. The argument is a per-time high-probability bound, not a simultaneous guarantee over an unlimited history.

Equations 11–17
E[at+1​(x,y)]=E[at​(x−1,y)]+E[at​(x+1,y)]+E[at​(x,y−1)]+E[at​(x,y+1)]4.\operatorname*{E}\left[a_{t+1}\left(x,y\right)\right]=\frac{\operatorname*{E}\left[a_{t}\left(x-1,y\right)\right]+\operatorname*{E}\left[a_{t}\left(x+1,y\right)\right]+\operatorname*{E}\left[a_{t}\left(x,y-1\right)\right]+\operatorname*{E}\left[a_{t}\left(x,y+1\right)\right]}{4}.
at​(B)=∑(x,y)∈Bat​(x,y).a_{t}\left(B\right)=\sum_{\left(x,y\right)\in B}a_{t}\left(x,y\right). (11)
⌊at​(B)​GL2⌋\left\lfloor\frac{a_{t}\left(B\right)G}{L^{2}}\right\rfloor (12)
⌊E[at(B)]GL2⌋.\left\lfloor\frac{\operatorname*{E}\left[a_{t}\left(B\right)\right]G}{L^{2}}\right\rfloor. (13)
Pr[|at(B)−E[at(B)]|>δE[at(B)]]<2exp(−E[at(B)]δ23).\Pr\left[\left|a_{t}\left(B\right)-\operatorname*{E}\left[a_{t}\left(B\right)\right]\right|>\delta\operatorname*{E}\left[a_{t}\left(B\right)\right]\right]<2\exp\left(-\frac{\operatorname*{E}\left[a_{t}\left(B\right)\right]\delta^{2}}{3}\right). (14)
Pr[|at(B)−E[at(B)]|>L2G]<2exp(−L43G2E[at(B)]).\Pr\left[\left|a_{t}\left(B\right)-\operatorname*{E}\left[a_{t}\left(B\right)\right]\right|>\frac{L^{2}}{G}\right]<2\exp\left(-\frac{L^{4}}{3G^{2}\operatorname*{E}\left[a_{t}\left(B\right)\right]}\right). (15)
2​exp⁡(−L23​G2).2\exp\left(-\frac{L^{2}}{3G^{2}}\right). (16)
L≫G​3​ln⁡(2​n2)=Θ⁡(G​log⁡n),L\gg G\sqrt{3\ln\left(2n^{2}\right)}=\Theta\left(G\sqrt{\log n}\right), (17)
Concept demonstration

Open image ↗