Problem 3

What is the analogue of geometry for the configuration space of a cellular automaton?

Several simple observations may be made. First, if the cellular automaton lattice is more than one-dimensional, one may consider Lyapunov exponents in different directions on this lattice. A remarkable empirical observation is that for cellular automata these exponents are approximately equal in all directions, even those not along the axes of the lattice, and even for cellular automata with asymmetric rules [12]. Second, in a one-dimensional cellular automaton one may consider Lyapunov exponents for subsets of configurations, or for particular components of configurations. For example, for a cellular automaton in which a class 1 component involving sites with values 0 and 2 is superimposed on class 3 behaviour involving sites with values 0 and 1, the Lyapunov exponent is positive in the ``value 1'' direction, and negative in the ``value 2'' direction. In general it seems that the cellular automaton evolution induces a form of geometry on the configuration space [13]. But the details are unclear; one does not know, for example, the analogue of the tangent space considered in continuous dynamical systems.

previous  l  next