Introduction

This appendix gives tables of properties of one-dimensional cellular automata with two possible values at each site (), and with rules depending on nearest neighbours (). These cellular automata are some of the simplest that can be constructed. Yet they are already capable of a great diversity of highly complex behaviour. The tables in this appendix attempt to capture some of this behaviour, both pictorially and numerically.

There are possible rules for , cellular automata. Table 1 gives forms for these rules, together with simple equivalences among them.

Tables 2 and 3 show patterns produced by evolution according to all possible inequivalent rules, starting from ``typical'' disordered or random initial conditions. Several general classes of qualitative behaviour are seen (see pages 115--157 in this book):

1. A fixed, homogeneous, state is eventually reached (e.g. rules 0, 8, 136).
2. A pattern consisting of separated periodic regions is produced (e.g. rules 4, 37, 56, 73).
3. A chaotic, aperiodic, pattern is produced (e.g. rules 18, 45, 146).
4. Complex, localized structures are generated (e.g. rule 110). (This behaviour is clearly visible in the pictures of table 15.)

Much of the data in this appendix can be understood in terms of this classification.

The patterns produced with a particular rule by evolution from different disordered initial states are qualitatively similar. Nevertheless, changes in initial conditions can lead to detailed changes in the configurations produced. Table 4 shows the pattern of differences produced by single-site changes in initial conditions. For class 1 rules, the changes always die out. For class 2 rules, they may persist, but remain localized. Class 3 rules, however, show ``instability'': small changes in initial conditions can lead to an ever-expanding region of differences. ``Information'' on the initial state thus propagates, typically at a fixed speed, through the cellular automaton. In class 4 cellular automata, such information transmission occurs irregularly, through motion of specific localized structures.

Table 6 gives the values of some statistical quantities which characterize some of the behaviour seen in tables 2, 3 and 4. The definitions of entropies and Lyapunov exponents for cellular automata (see pages 115--157 in this book) are closely analogous to those for conventional continuous dynamical systems.

Tables 2, 3, 4 and 6 concern the generic behaviour of cellular automata with ``typical'' disordered initial conditions. The generation of complexity in cellular automata is however perhaps more clearly illustrated by evolution from particular, simple, initial conditions, as in table 5. With such initial conditions, some cellular automaton rules yield simple or regular patterns. But other rules yield highly complex patterns, which seem in many respects random.

Tables 2 through 6 suggest that many different , cellular automata exhibit similar behaviour. Table 1 gives some simple equivalences between rules. Table 7 gives equivalences arising from more complex transformations. Often different regions in a cellular automaton will form ``domains'' which show different equivalences.

Table 8 gives further relations between rules, in the form of factorizations which express one rule as compositions of others.

An important feature of cellular automata is their capability for ``self organization''. Even starting from arbitrary disordered or random initial conditions, their time evolution can pick out particular ``ordered'' states. Tables 9 through 11 give mathematical characterizations of the sets of configurations that can occur in the evolution of , cellular automata. Table 9 concerns blocks of site values which are filtered out by the cellular automaton evolution.

The complete set of configurations produced after any finite number of time steps can be described in terms of regular formal languages (see pages 159--202 in this book). Tables 10 and 11 give the values of quantities which characterize the certain aspects of the ``complexity'' of these languages.

The behaviour of class 3 and 4 cellular automata often seems to be so complex that its outcome cannot be determined except by essentially performing a direct simulation. Tables 10 and 11 may provide some quantitative basis for this supposition. Table 12 gives a more direct measure of the difficulty of computing the outcome of cellular automaton evolution in the context of a simple computational model involving Boolean functions.

The results for most of the tables here are for cellular automata on lattices with an infinite number of sites. Tables 13 and 14 give some of the more complete results that can be obtained for cellular automata on finite lattices (or with spatially periodic configurations). Table 13 shows fragments of the state transition diagrams which describe the global evolution of finite cellular automata. Table 14 plots some of their overall properties.

Many of the , cellular automata show highly complex behaviour. Such behaviour is probably most evident in rule 110. Table 15 gives some properties of the particle-like structures which are found in this rule. One suspects that with appropriate combinations of these structures, it should be possible to perform universal computation.

The final table shows patterns produced by reversible generalizations of the standard , cellular automata. Qualitatively similar behaviour is again seen.

It is remarkable that with such simple construction, the , cellular automata can show such complex behaviour. The tables in this appendix give some first attempts at characterizing and quantifying this behaviour. Much, however, still remains to be done.

next