Compression-based investigation of the dynamical properties of cellular automata and other systems

Abstract

A method for studying the qualitative dynamical properties of abstract computing machines based on the approximation of their program-size complexity using a general lossless compression algorithm is presented. It is shown that the compression-based approach classifies cellular automata (CA) into clusters according to their heuristic behavior, with these clusters showing a correspondence with Wolfram's main classes of CA behavior. A compression based method to estimate a characteristic exponent to detect phase transitions and measure the resiliency or sensitivity of a system to its initial conditions is also proposed. A conjecture regarding the capability of a system to reach computational universality related to the values of this phase transition coefficient is formulated. These ideas constitute a compression-based framework for investigating the dynamical properties of cellular automata and other systems.

28 pages. This version includes the conjecture relating the transition coefficient to computational universality. Camera ready version

Cited by in corpus (4)

• Complexity and Information: Measuring Emergence, Self-organization, and Homeostasis at Multiple Scales
• Lempel-Ziv complexity analysis of one dimensional cellular automata
• Collective Intelligence for Deep Learning: A Survey of Recent Developments
• Definition and Identification of Information Storage and Processing Capabilities as Possible Markers for Turing-universality in Cellular Automata