^{1}, Owen J. Brison

^{3}and Jason A. C. Gallas

^{4}

### Abstract

We study the dynamics of patterns exhibited by rule 52, a totalistic cellular automaton displaying intricate behaviors and wide regions of active/inactive synchronization patches. Systematic computer simulations involving initial configurations reveal that all complexity in this automaton originates from random juxtaposition of a very small number of * interfaces * delimiting active/inactive patches. Such interfaces are studied with a sidewise * spatial updating algorithm*. This novel tool allows us to prove that the interfaces found empirically are the only interfaces possible for these periods, independently of the size of the automata. The spatial updating algorithm provides an alternative way to determine the dynamics of automata of *arbitrary size*, a way of taking into account the complexity of the connections in the lattice.

Cellular automata are remarkable test beds combining phenomena as diverse as chaotic attractors, artificial life, and universal computation, in a suitable setup for probing directly the interrelation between networkstructure and dynamics.

^{1–5}In this framework, the purpose of this paper is to report from a fresh point of view an investigation of the high-complexity exhibited by rule 52, a prototypical one-dimensional binary automaton reputedly of class 4, defined in Eq. (2) below. Instead of focusing on the time-evolution of the automaton as usual,

^{6–9}here we explore the

*spatial connectivity*and structure of the lattice. More specifically, rather than following the time-evolution of the automaton, we set out to determine which spatial configurations are allowed generically in the architecture combining lattice and dynamical rule. In contrast with the standard approach, from the outset we work with lattices of indefinite spatial size , avoiding the need for subsequently investigating the dynamics of automata of increasingly larger values of in order to find those behaviors which subsist in the thermodynamic limit . As shown below, considerations of the spatialstructure of the automaton may be translated into an efficient algorithm to construct and classify explicitly all complex structures and patterns supported by a given architecture.

The authors are indebted to Peter Grassberger and to Antonio Politi for helpful comments on this manuscript. J. G. F. thanks Fundação para a Ciência e Tecnologia, Portugal, for a Doctoral Fellowship and for supporting her study stays in Brazil. O. J. B. thanks the Centro de Estruturas Lineares e Combinatórias da Universidade de Lisboa for partial support. J. A. C. G. thanks Conselho Nacional de Desenvolvimento Científico e Tecnológico, Brazil, for a Senior Research Fellowship. He also thanks support from the Air Force Office of Scientific Research, through Contract No. FA9550-07-1-0102.

I. INTRODUCTION

II. COMPUTER SIMULATIONS

III. THE ELEMENTARY INTERFACES

IV. SYNCHRONIZATION AND COMPLEXITY

V. ALGORITHM FOR SPATIAL UPDATING

VI. SUMMARY AND OUTLOOK

### Key Topics

- Interface structure
- 23.0
- Cellular automata
- 8.0
- Networks
- 8.0
- Interface thermodynamics
- 7.0
- Computer interfaces
- 6.0

## Figures

(Color online) Typical complex spatio-temporal patterns produced by rule 20. After a first transient (short-lived), the surviving nonquiescent activity is that of a few localized *gliders*: three stationary and time-periodic gliders located roughly at the center of the figure, and a traveling glider on the right. The collision between traveling and static gliders defines a second transient (long-lived) of the system, when the dynamics under rule 20 invariably collapses into tame class 2 behavior (Refs. ^{ 30 and 31 } ).

(Color online) Typical complex spatio-temporal patterns produced by rule 20. After a first transient (short-lived), the surviving nonquiescent activity is that of a few localized *gliders*: three stationary and time-periodic gliders located roughly at the center of the figure, and a traveling glider on the right. The collision between traveling and static gliders defines a second transient (long-lived) of the system, when the dynamics under rule 20 invariably collapses into tame class 2 behavior (Refs. ^{ 30 and 31 } ).

(Color online) Typical complex spatio-temporal patterns generated by rule 52. Top: Asymptotically, the system settles into arbitrarily large patches of synchronized activity, 0 (white) or 1 [black (purple online)], interconnected by transition interfaces where cyclic activity occurs. Gliders may subsist *inside* individual patches but remain ephemeral as in rule 20. Bottom: Transition interfaces are static or may travel. Periodic boundary conditions eventually lead to *collisions* of interfaces and larger regions of synchronized activity.

(Color online) Typical complex spatio-temporal patterns generated by rule 52. Top: Asymptotically, the system settles into arbitrarily large patches of synchronized activity, 0 (white) or 1 [black (purple online)], interconnected by transition interfaces where cyclic activity occurs. Gliders may subsist *inside* individual patches but remain ephemeral as in rule 20. Bottom: Transition interfaces are static or may travel. Periodic boundary conditions eventually lead to *collisions* of interfaces and larger regions of synchronized activity.

(Color online) The elementary interfaces needed to produce all asymptotic complexities computed for rule 52. Interfaces A–E bridge patches with backgrounds of different colors. Time always evolves downwards, here and subsequently.

(Color online) The elementary interfaces needed to produce all asymptotic complexities computed for rule 52. Interfaces A–E bridge patches with backgrounds of different colors. Time always evolves downwards, here and subsequently.

(Color online) Elementary structures F and G which may be regarded as localized structures that may or may not travel, or interfaces bridging two identical but spatially separated phases. The traveling glider is not elementary but a juxtaposition of and , the conjugate of . It travels at the “speed of light” in the system: one cell per time step. Glider travels at cell per step.

(Color online) Elementary structures F and G which may be regarded as localized structures that may or may not travel, or interfaces bridging two identical but spatially separated phases. The traveling glider is not elementary but a juxtaposition of and , the conjugate of . It travels at the “speed of light” in the system: one cell per time step. Glider travels at cell per step.

(Color online) Gliders arising when interfaces are glued together. Top: the simplest motifs surviving on a white background representing zeros. Middle: conjugates of the gliders in the top row, white structures surviving on a black background of ones. Bottom: “fat” gliders, i.e., the same gliders seen on the top row but now with “inflated” inner cores of ones. Note the different possibilities of combining interfaces.

(Color online) Gliders arising when interfaces are glued together. Top: the simplest motifs surviving on a white background representing zeros. Middle: conjugates of the gliders in the top row, white structures surviving on a black background of ones. Bottom: “fat” gliders, i.e., the same gliders seen on the top row but now with “inflated” inner cores of ones. Note the different possibilities of combining interfaces.

(Color online) Top: Static hybrid gliders formed by juxtaposing distinct elementary interfaces. The four black sites separating interfaces may be inflated arbitrarily, as indicated in Fig. 5 . Center: static gliders formed by dephasings due to the different ways of juxtaposing identical period-3 interfaces. Note that has “rotational symmetry” with respect to its central axis while and have “helicoidal symmetry,” i.e., involve a reflection plus a one time-step shift as hinted by the additional coloring. The minimum distance between interfaces is larger for the gliders located on the left, to prevent white cells from interacting. Bottom: Hybrid gliders due to the three possible time-dephasings between different period-3 interfaces.

(Color online) Top: Static hybrid gliders formed by juxtaposing distinct elementary interfaces. The four black sites separating interfaces may be inflated arbitrarily, as indicated in Fig. 5 . Center: static gliders formed by dephasings due to the different ways of juxtaposing identical period-3 interfaces. Note that has “rotational symmetry” with respect to its central axis while and have “helicoidal symmetry,” i.e., involve a reflection plus a one time-step shift as hinted by the additional coloring. The minimum distance between interfaces is larger for the gliders located on the left, to prevent white cells from interacting. Bottom: Hybrid gliders due to the three possible time-dephasings between different period-3 interfaces.

(Color online) The basic construction used for sidewise updating of the automaton, i.e., for *spatial* updating, and to locate periodic patterns, illustrated here for the simplest scenario possible: fixed point (i.e., period 1). Since , the first site of the interface is *ambiguous*, i.e., , where or , because both values satisfy rule 52, Eq. (2) . Whatever the value chosen, it must be copied downward, as indicated by the arrow, to ensure period-1. The evolution for the nontrivial choice is shown in Fig. 8 .

(Color online) The basic construction used for sidewise updating of the automaton, i.e., for *spatial* updating, and to locate periodic patterns, illustrated here for the simplest scenario possible: fixed point (i.e., period 1). Since , the first site of the interface is *ambiguous*, i.e., , where or , because both values satisfy rule 52, Eq. (2) . Whatever the value chosen, it must be copied downward, as indicated by the arrow, to ensure period-1. The evolution for the nontrivial choice is shown in Fig. 8 .

(Color online) Proof that rule 52 supports only one elementary interface/glider of period one. (a) The bit highlighted is determined by the left-neighbor of the starting configuration. Yellow (light gray) indicates that the construction may proceed since none of the deadlock configurations discussed in Fig. 10 below was found. (b–e) The bit determined in the previous step is copied and a new bit is determined. (f) A new darker color (shading) is used to indicate that an ambiguous situation is reached, when both 0 and 1 are valid choices. Repeated choices increase the size of the synchronization patch of 1, producing the interface , the conjugate of in Fig. 2 , preserving the possibility of an ambiguous choice indefinitely (see text).

(Color online) Proof that rule 52 supports only one elementary interface/glider of period one. (a) The bit highlighted is determined by the left-neighbor of the starting configuration. Yellow (light gray) indicates that the construction may proceed since none of the deadlock configurations discussed in Fig. 10 below was found. (b–e) The bit determined in the previous step is copied and a new bit is determined. (f) A new darker color (shading) is used to indicate that an ambiguous situation is reached, when both 0 and 1 are valid choices. Repeated choices increase the size of the synchronization patch of 1, producing the interface , the conjugate of in Fig. 2 , preserving the possibility of an ambiguous choice indefinitely (see text).

(Color online) Initial developments for proving existence of interfaces/gliders of period 3, when two sites are considered simultaneously. (a) A pair of 1s is required on the right. (b) The choice and violates rule 52. (c) Deadlock generated by the choice . Conclusion: may only be 10 or 01. These two choices are analyzed in Fig. 12 .

(Color online) Initial developments for proving existence of interfaces/gliders of period 3, when two sites are considered simultaneously. (a) A pair of 1s is required on the right. (b) The choice and violates rule 52. (c) Deadlock generated by the choice . Conclusion: may only be 10 or 01. These two choices are analyzed in Fig. 12 .

(Color online) Key properties of rule 52. Two uppermost panels: *Ambiguous* configurations, when the binary value of site at time is true independently of the value of at time . Two lowest panels: *Deadlock* configurations, when the value at time is impossible, independently of . The precise location of and in the 5-cells neighborhood is irrelevant. The colors marking ambiguous and deadlock configurations will be used subsequently.

(Color online) Key properties of rule 52. Two uppermost panels: *Ambiguous* configurations, when the binary value of site at time is true independently of the value of at time . Two lowest panels: *Deadlock* configurations, when the value at time is impossible, independently of . The precise location of and in the 5-cells neighborhood is irrelevant. The colors marking ambiguous and deadlock configurations will be used subsequently.

(Color online) Proof that there is only one possible arrangement leading to an elementary structure of period-2, that is labeled in Fig. 4 . The ambiguity is preserved as the structure grows to the right by selecting . Selecting in the manner shown in Fig. 9(a) will generate another structure . Arbitrary alternations of structures are possible by suitably intercalating choices and .

(Color online) Proof that there is only one possible arrangement leading to an elementary structure of period-2, that is labeled in Fig. 4 . The ambiguity is preserved as the structure grows to the right by selecting . Selecting in the manner shown in Fig. 9(a) will generate another structure . Arbitrary alternations of structures are possible by suitably intercalating choices and .

(Color online) Proof of the existence of just two elementary interface/gliders of period three for the pair of possible initial configurations. Top two rows: Development of the cases and discussed in Fig. 9(b) . Bottom two rows: Development for the remaining possibility of initial configurations, both leading to deadlock.

(Color online) Proof of the existence of just two elementary interface/gliders of period three for the pair of possible initial configurations. Top two rows: Development of the cases and discussed in Fig. 9(b) . Bottom two rows: Development for the remaining possibility of initial configurations, both leading to deadlock.

(Color online) Spatial information flow for period 7. The pattern above may be extended indefinitely to the right. After a *spatial transient* of 32 sites one finds a spatial period of 49 sites. Note that it is impossible to find this asymmetric pattern using the time-honored expedient of time-evolving initial conditions on finite lattices under periodic boundary conditions. It can only be found using sidewise spatial updating.

(Color online) Spatial information flow for period 7. The pattern above may be extended indefinitely to the right. After a *spatial transient* of 32 sites one finds a spatial period of 49 sites. Note that it is impossible to find this asymmetric pattern using the time-honored expedient of time-evolving initial conditions on finite lattices under periodic boundary conditions. It can only be found using sidewise spatial updating.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content