I’ve written a new paper under the title “Compression-based investigation of the dynamical properties of cellular automata and other systems”.

A pdf version of the paper from a Mathematica notebook is available online at ArXiv

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 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.
——————————

Stephen Wolfram proposed a classification of cellular automaton rules into four types, according to the results of evolving the system from a “disordered” (namely random) initial configuration:

1. Evolution leads to a homogeneous state.
2. Evolution leads to a set of separated simple stable or periodic structures.
3. Evolution leads to a chaotic pattern.
4. Evolution leads to complex localized structures, sometimes long-lived.

An interesting question about Wolfram’s classification concerns its dependence on the initial condition–chiefly because the classification was originally meant to be constructed by visual inspection over the evolution of a CA, and as we know, the evolution of a CA depends on its initial condition. This has been a major critic (Eppstein) of Wolfram’s classification, because somehow the classification should be based on the evolution from an unordered (random) configuration and no on initially ordered configuration.

Nevertheless, the classification is based on the potential of a CA to evolve into any of the possible behaviors from at least one initial configuration (the question is of course not finitely answerable since there is an infinite number of possible initial configurations). But that in the end one ends up analyzing only a finite number of particular cases, including an order and a disordered initial configuration. Wolfram’s classification might therefore be seen as being dependent on the initial condition of a CA.

It is not a surprise that one can for example construct a CA belonging to more than one of Wolfram’s four classes when starting from different initial configurations. Think of rule 110 for example. Rule 110 can in principle be made to look as if it belonged to any class because, given its universality, it is capable of simulating any other CA. Rule 110 belongs to class 4 because it is capable of universal computation— one can set up an initial configuration to ‘program’ rule 110 to carry out any computation (it is the very basic concept of a programmable computer).

For every CA rule there is a definite (but in general undecidable ) answer to the question whether or not it is capable of universal computation (or in reachability terms, whether a CA will develop into a certain configuration). The question only makes sense if the evolution of a CA depends on its initial configuration. No rule can be universal that fixes the initial configuration once and for all (there would be no way to input an instruction and carry out an arbitrary computation).

On the other hand, some rules, such as Rule 0, don’t produce one or another configuration relative to variant initial configurations. No matter how you change the initial condition, there is no way to make it compute something other than what it actually computes for every other initial configuration.

In light of all this, David Eppstein’s critique of Wolfram’s classification is vacuous because obvious from my point of view. His main argument is that there are CAs that can be made to look as if they belonged to all classes by modifying their initial conditions. Which is obviously true!

A CA belongs to a certain class until, given another initial configuration, it is made to behave as if it belonged to another, more powerful one (assuming some kind of hierarchy, at least between classes 1 and 2 and classes 3 and 4).

My paper on compression-based investigations shows that Wolfram’s heuristic classification can actually be quantified by a measure which is clearly dependent on the initial conditions while also being capable of detecting sensitivity to initial configurations and hence of replacing the visual inspection.

This represents a formal approach to Wolfram’s classification process, and a method to determine to what class a CA belongs which is compatible with what Stephen Wolfram himself has proposed in his NKS book.

Notice that the paper is a pdf file generated from a Mathematica notebook. Hence some images (e.g. cells indicating an initial configuration) are not optimal. A version in LaTeX is being prepared and will replace this version.

Last Modified : November 11th, 2009 Filed under : Algorithmic information theory, Computer Science, New Ideas Navigate : Previous post / Next post