Excerpt

Measuring  the  emergent  complexity  of  a  complex  system  has  itself become a complex process—and is still ongoing. Over the past few decades, an ever-expanding realm of researchers from various disciplines have come up with a wide variety of different metrics, starting from different viewpoints and answering different questions that can often somehow be related to each other. A root cause of this expansion is the difficulty of pinning down the exact problem. Or as Seth Lloyd (2001) aptly put it: “A historical analog to the problem of measuring complexity  is  the  problem  of  describing  electromagnetism  before Maxwell’s equations.”

Initially,  many  researchers  were  in  pursuit  of  the  complexity measure:  one  formula  or  algorithm  that  quantifies  the  amount  of complexity  in  any  given  program  or  pattern.  The  sheer  variety  of measures that resulted has shifted the focus to look for a complexity measure: a choice that depends on the context, the research question, and the assumptions one is willing to make.

In this light, James Crutchfield’s 1994 paper can be seen as a novel approach in the statistical description of complexity measures, but with a key distinction that has crucial consequences.

Bibliography

Arkin, R. C. 1998. Behavior-Based Robotics. Cambridge, MA: MIT Press.

Barnett, N., and J. Crutchfield. 2015. “Computational Mechanics of Input–Output Processes: Structured Transformations and the ϵ-Transducer.” Journal of Statistical Physics 161:404–451. https://doi.org/10.48550/arXiv.1412.2690.

Bennett, C. 1982. “The Thermodynamics of Computation—A Review.” International Journal of Theoretical Physics 21:905–40. https://doi.org/10.1007/BF02084158.

Boyd, A., D. Mandal, and J. P. Crutchfield. 2016. “Identifying Functional Thermodynamics in Autonomous Maxwellian Ratchets.” New Journal of Physics 18 (2): 023049. https://doi.org/10.1088/1367-2630/18/2/023049.

— . 2017. “Leveraging Environmental Correlations: The Thermodynamics of Requisite Variety.” Journal of Statistical Physics 167:1555–85. https://doi.org/10.1007/s10955-017-1776-0.

Boyd, A. B., J. P. Crutchfield, and M. Gu. 2022. “Thermodynamic Machine Learning through Maximum Work Production.” New Journal of Physics 24. https://doi.org/10.1088/1367-2630/ac4309.

Brodu, N. 2011. “Reconstruction of Epsilon-Machines in Predictive Frameworks and Decisional States.” Advances in Complex Systems 14 (05): 761–94. https://doi.org/10.1142/S0219525911003347.

Casey, M. 1996. “The Dynamics of Discrete-Time Computation, with Application to Recurrent Neural Networks and Finite State Machine Extraction.” Neural Computation 8 (6): 1135–1178. https://doi.org/10.1162/neco.1996.8.6.1135.

Crutchfield, J. P. 1994. “The Calculi of Emergence: Computation, Dynamics, and Induction.” Physica D: Nonlinear Phenomena 75 (1-3): 11–54. https://doi.org/10.1016/0167-2789(94)90273-9.

Elliott, T., C. Yang, F. C. Binder, A. J. P. Garner, J. Thompson, and M. Gu. 2020. “Extreme Dimensionality Reduction with Quantum Modeling.” Physical Review Letters 125:260501. https://doi.org/10.1103/PhysRevLett.125.260501.

Garner, A., Q. Liu, J. Thompson, and V. Vedral. 2017. “Provably Unbounded Memory Advantage in Stochastic Simulation Using Quantum Mechanics.” New Journal of Physics 19:103009. https://doi.org/10.1088/1367-2630/aa82df.

Gu, M., K. Wiesner, E. Rieper, and V. Vedral. 2012. “Quantum Mechanics Can Reduce the Complexity of Classical Models.” Nature Communications 3 (1): 762. https://doi.org/10.1038/ncomms1761.

James, R. G., C. J. Ellison, and J. P. Crutchfield. 2011. “Anatomy of a Bit: Information in a Time Series Observation.” Chaos: An Interdisciplinary Journal of Nonlinear Science 21 (3). https://doi.org/10.48550/arXiv.1105.2988.

Jurgens, A. M., and J. P. Crutchfield. 2021. “Divergent Predictive States: The Statistical Complexity Dimension of Stationary, Ergodic Hidden Markov Processes.” Chaos 31 (8): 083114. https://doi.org/10.1063/5.0050460.

Koul, A., S. Greydanus, and A. Fern. 2018. Learning Finite State Representations of Recurrent Policy Networks. https://doi.org/10.48550/arXiv.1811.12530. arXiv: 1811.12530[cs.LG]. https://arxiv.org/abs/1811.12530.

Lloyd, S. 2001. “Measures of Complexity: A Non-Exhaustive List.” IEEE Control Systems Magazine 21 (4): 7–8. https://doi.org/10.1109/MCS.2001.939938.

Loomis, S. P., and J. P. Crutchfield. 2020. “Thermal Efficiency of Quantum Memory Compression.” Physical Review Letters 125 (2): 020601. https://doi.org/10.1103/PhysRevLett.125.020601.

Quax, R., O. Har-Shemesh, and P. M. A. Sloot. 2017. “Quantifying Synergistic Information Using Intermediate Stochastic Variables.” Entropy 19 (2): 85. https://doi.org/10.3390/e19020085.

Ray, A. 2004. “Symbolic Dynamic of Complex Systems for Anomaly Detection.” Signal Processing 84 (7):1115–30. https://doi.org/10.1016/j.sigpro.2004.03.011.

Rissanen, J. 1987. “Stochastic Complexity.” Journal of Royal Statistical Society 49 (3). https://doi.org/10.1111/j.2517-6161.1987.tb01694.x.

Shai, A. S., S. E. Marzen, L. Teixeira, A. G. Oldenziel, and P. M. Riechers. 2024. “Transformers Represent Belief State Geometry in their Residual Stream.” arXiv, https://doi.org/10.48550/arXiv.2405.15943.

Yang, Y., G. Chiribella, and M. Hayashi. 2018. “Quantum Stopwatch: How to Store Time in a Quantum Memory.” Proceedings of the Royal Society A 474 (2213): 20170773. https://doi.org/10.1098/rspa.2017.0773.

Zhang, A., Z. C. Lipton, L. Pineda, K. Azizzadenesheli, A. Anandkumar, L. Itti, J. Pineau, and T. Furlanello. 2021. “Learning Causal State Representations of Partially Observable Environments.” https://doi.org/10.48550/arXiv.1906.10437. arXiv: 1906.10437 [cs.LG].

BACK TO Foundational Papers in Complexity Science