Foundational Papers in Complexity Science pp. 1735–1792
DOI: 10.37911/9781947864542.59
The Emergent Behavior of Computer Programs of Short Description Length in Discrete Time and Discrete Space
Author: Hector Zenil, University of Cambridge
Excerpt
The mathematical formalization and phenomenological description of complex behavior emerging from simple (e.g., discrete) deterministic dynamical systems has traditionally been traced back to authors such as Henri Poincaré, Stephen Smale, Michel Hénon, or—in the context of digital systems—to Alan Turing, John von Neumann, Nils Aall Barricelli, or John Conway. However, most authors in dynamical systems dealt with discrete time but not discrete space, and Turing, von Neumann, Barricelli, and Conway never made any assertion as to the pervasiveness of emergent complex phenomena beyond specific constructions in discrete space.
Turing universality does imply that computer programs are capable of unbounded complexity, even running on discrete space, by virtue of being able to execute any other computer program (including complex ones) or approximate any computable mathematical function of any apparent complexity. However, the actual length of the encodings and the pervasiveness of such behavior for typical inputs (or random executed programs) was unknown. It was Gregory Chaitin and Ray Solomonoff who started asking questions about the distribution of possible outcomes from running random computer programs. Their results relate to mathematical limits and large constants that were seen as having limited practical value.
Bibliography
Riedel, J., and H. Zenil. 2018. “Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Universality.” International Journal of Unconventional Computing 13 (14-15): 309–357. https://doi.org/10.48550/arXiv.1510.01671.
Wolfram, S. 1983. “Statistical Mechanics of Cellular Automata.” Reviews of Modern Physics 55:601–644. https://doi.org/10.1103/RevModPhys.55.601.
—. 2002. A New Kind of Science. 23–60, 112, 865–866. Champaign, IL: Wolfram Media.
—. 2020. “A Class of Models with the Potential to Represent Fundamental Physics.” Complex Systems 29 (2): 107–536. https://doi.org/10.25088/ComplexSystems.29.2.107.
Zenil, H. 2013. Asymptotic Behaviour and Ratios of Complexity in Cellular Automata Rule Spaces. Vol. 23. 9. https://doi.org/10.48550/arXiv.1304.2816.
Zenil, H., N. A. Kiani, F. S Abrahão, and J. N. Tegnér. 2020. “Algorithmic Information Dynamics.” Revision #200719, Scholarpedia 15 (7): 53143. https://doi.org/10.4249/scholarpedia.53143.
Zenil, H., N. A. Kiani, F. Marabita, Y. Deng, S. Elias, A. Schmidt, G. Ball, and J. Tegnér. 2019. “An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems.” Science, https://doi.org/S2589-0042(19)30270-6.