Compression-Based Investigation of the Dynamical Properties of Cellular Automata and Other Systems
Hector Zenil
Laboratoire d'Informatique Fondamentale de Lille (USTL/CNRS)
and
Institut d'Histoire et de Philosophie des Sciences et des Techniques (CNRS/Paris 1/ENS Ulm)
hector.zenil-chavez@malix.univ-paris1.fr
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 into clusters according to their heuristic behavior. These clusters show a correspondence with Wolfram's main classes of cellular automata behavior. A Gray code-based numbering scheme is developed for distinguishing initial conditions. A compression-based method to estimate a characteristic exponent for detecting phase transitions and measuring 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.
