Cellular automata with coarse-graining invariant orbits

Andre Barbé , Heinz-Otto Peitgen (b), Gencho Skordev(b,c)Center for Complex Systems and Visualisation, University of Bremen

In the attempt to contribute to an understanding of emergent complex behaviour in dynamical systems, we have continued the study concerning the nonclassical extension of cellular automata (CA) whose orbits (state-time evolution patterns) are not only determined by a local evolution rule , but also by a global condition . This generates orbits whose complexity features may range between complete order (periodicity) and complete disorder (randomness). The global condition is coarse-graining invariance (CGI), a well-known concept from renormalization theory used in the study of citical phenomena in physics, but here applied in the discrete algebraic domain in which the CA-behaviour is defined.

a.

The three-dimensional CGI orbits of two-dimensional linear CA over a finite field were investigated, as a nontrivial extension of the two-dimensional CGI orbits for one-dimensional CA studied before. The orbits can be found by solving a particular kind of recursive equations which contain a rescaling term. The solution grows from some seed which, in contrast with the one-dimensional case, has infinite support. This leads to three categories of orbits (as opposed to a single one in the one-dimensional case). Complex order emerges from random seeds as well as from seeds of simple order (fig.1). The automaticity property of the orbit, which holds for the one-dimensional case , generally breaks down for the two-dimensional case (automaticity being a complexity category for sequences explicited in terms of finite automata, substitution systems and decimations of the sequence ).

 

Figure 8: (a) Part of an initial configuration of a two-dimensional coarse-graining invariant cellular automaton (quasiperiodic seed ) ; (b) shows a hidden structure in (a).

b.

The automaticity property for one-dimensional coarse-graining invariant linear CA, only known as a conjecture before, has been proven to hold for linear CGI-CA defined over the ring of integers modulo a prime power (an extension of the finite field CAs considered before). The relationship between solutions of such CGI-problems for different powers of a given prime was also investigated.

c.

Decimation of a sequence is a particular method of coarse-graining which constructs a new sequence by selecting elements of the original sequence at regular distances. One-dimensional decimation- invariant sequences were studied: a method for solving the underlying renormalizing equations and for determining the kernel graph (an automaticity-related graph) was developed. The size of the kernel graph and the related substitution system form a complexity measure of the sequence.