Throughout the natural and artificial world one observes phenomena of great complexity. Yet research in physics and to some extent biology and other fields has shown that the basic components of many systems are quite simple. It is now a crucial problem for many areas of science to elucidate the mathematical mechanisms by which large numbers of such simple components, acting together, can produce behaviour of the great complexity observed. One hopes that it will be possible to formulate universal laws that describe such complexity.

The second law of thermodynamics is an example of a general principle that governs the overall behaviour of many systems. It implies that initial order is progressively degraded as a system evolves, so that in the end a state of maximal disorder and maximal entropy is reached. Many natural systems exhibit such behaviour. But there are also many systems that exhibit quite opposite behaviour, transforming initial simplicity or disorder into great complexity. Many physical phenomena, among them dendritic crystal growth and fluid turbulence are of this kind. Biology provides the most extreme examples of such self-organization.

The approach that I have taken over the last couple of years is to study mathematical models that are as simple as possible in formulation, yet which appear to capture the essential features of complexity generation. My hope is that laws found to govern these particular systems will be sufficiently general to be applicable to a wide range of actual natural systems.

The systems that I have studied are known as cellular automata. In the simplest case, a cellular automaton consists of a line of sites. Each site carries a value 0 or 1. The configurations of the system are thus sequences of zeroes and ones. They evolve in a series of time steps. At each step, the value of each site is updated according to a specific rule. The rule depends on the value of a site, and the values of say its two nearest neighbours. So for example, the rule might be that the new site value is given by the sum of the old value of the site and its nearest neighbours, reduced modulo two (i.e. the remainder after division of the sum by two).

Even though the construction of cellular automata is very simple, their behaviour can be very complicated. And as a consequence, their analysis can be correspondingly difficult. In fact, there are reasons of principle to expect that there are no general methods that can universally be applied.

The first step in studying cellular automata is to simulate them, and see explicitly how they behave. Figure 1 shows some examples of cellular automata evolving from simple seeds. In each picture, the cellular automaton starts on the top line from an initial state in which all the sites have value zero, except for one site in the middle, which has value one. Then successive lines down the page are calculated from the lines above by applying the cellular automaton rule at each site.

Figure 1(a) shows one kind of pattern that can be generated by this procedure. Even though the rule is very simple (it can be stated in just one sentence, or a simple formula), and the initial seed is likewise simple, the pattern produced is quite complicated. Nevertheless, it exhibits very definite regularities. In particular, it is self-similar or fractal, in the sense that parts of it, when magnified, are similar to the whole.

Figure 2 illustrates the application of a cellular automaton like the one in figure 1(a) to the study of a natural phenomenon: the growth of dendritic crystals, such as snowflakes (as investigated by Norman Packard). The cellular automaton of figure 1(a) is generalized to be on a planar hexagonal grid, rather than a line. Then a cellular automaton rule is devised to reproduce the microscopic properties of solidification. A set of partial differential equations provide a rather complete model for solidification. But to study the overall patterns of growth produced, one can use a model that includes only some specific features of the microscopic dynamics. The most significant feature is that a planar interface is unstable, and produces protrusions with some characteristic length scale. The sizes of the sites in the cellular automaton correspond to this length scale, and the rules that govern their evolution incorporate the instability. With this simple caricature of the microscopic laws, one obtains patterns apparently very similar to those seen in actual snowflakes. It remains to carry out an actual experiment to find out whether the model indeed reproduces all the details of snowflakes.

More: http://www.stephenwolfram.com/publications/articles/general/88-complex/2/tex t.html