Compression-Based Investigation of the Dynamical Properties of Cellular Automata and Other Systems
Laboratoire d'Informatique Fondamentale de Lille, Hector Zenil, Institut d'Histoire et de Philosophie des Sciences et des Techniques · Complex Systems · 2010
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 compressionbased 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 Gray code-based numbering scheme for initial conditions and 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, constituting a compression-based framework for investigating the dynamical properties of cellular automata and other systems.