Role of initial conditions in the classification of the rule space of cellular automata dynamics

Abstract

In the qualitative classification of cellular automata (CA) rules by Wolfram [Rev. Mod. Phys. 55, 601 (1983)], there exists a class of CA rules (called class 4) which exhibit complex pattern formation and long-lived dynamical activity (long transients). These properties of class 4 CA's has led to the conjecture that class 4 rules are universal Turing machines, i.e., they are bases for computational universality. We describe the embedding of a "small" universal turing machine, due to Minski [Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, NJ 1967)], into a cellular automaton rule table. This produces a collection of (k=18, r=1) cellular automata, all of which are computationally universal. However, we observe that these rules are distributed among the various Wolfram classes. More precisely, we show that the identification of the Wolfram class depends crucially on the set of initial conditions used to simulate the given CA. This work, among others, indicates that a description of complex systems and information dynamics may need a new framework for nonequilibrium statistical mechanics.