Cellular Automata
When Ilya Prigogine developed his theory of dissipative structures, he looked for the simplest examples he could describe mathematically. He found them in the catalytic loops of chemical oscillations, also known as “chemical clocks.” 1 These are not living systems, but the same kinds of catalytic loops are central to the metabolism of a cell, the simplest known living system. Therefore Prigogine’s model allows us to understand the essential structural features of cells in terms of dissipative structures.
Humberto Maturana and Francisco Varela followed a similar strategy when they developed their theory of autopoiesis, the pattern of organization of living systems. 2 They asked themselves: What is the simplest embodiment of an autopoietic network that can be described mathematically? Like Prigogine, they found that even the simplest cell was too complex for a mathematical model. On the other hand, they also realized that since the pattern of autopoiesis is the defining characteristic of a living system, there is no autopoietic system in nature simpler than a cell. So instead of looking for a natural autopoietic system, they decided to simulate one with a computer program.
Their approach was analogous to the Daisyworld model James Lovelock designed several years later. 3 But where Lovelock looked for the simplest mathematical simulation of a planet with a biosphere that would regulate its temperature, Maturana and Varela looked for the simplest simulation of a network of cellular processes embodying an autopoietic pattern of organization. This meant that they had to design a computer program simulating a network of processes, in which the function of each component is to help produce or transform other components in the network. As in a cell, this autopoietic network would also have to create its own boundary, which would participate in the network of processes and at the same time define its extension.
To find an appropriate mathematical technique for this task, Francisco Varela examined the mathematical models of selforganizing networks developed in cybernetics. The binary networks pioneered by McCulloch and Pitts in the 1940s did not offer sufficient complexity to simulate an autopoietic network, 4 but subsequent network models, known as “cellular automata,” turned out to provide the ideal techniques.
A cellular automaton is a rectangular grid of regular squares, or cells, like a chess board. Each cell can take on a number of different values and has a definite number of neighbor cells that can influence it. The pattern, or state,” of the entire grid changes in discrete steps according to a set of “transition rules” that apply simultaneously to every cell. Cellular automata are usually assumed to be completely deterministic, but random elements can easily be introduced into the rules, as we shall see.
These mathematical models are called “automata” because they were invented originally by John von Neumann to construct selfduplicating machines. Although such machines were never built, von Neumann showed in an abstract and elegant way that, in principle, this could be done. 5 Since then, cellular automata have been widely used both to model natural systems and to invent a large number of mathematical games. 6 Perhaps the best-known example is the game “Life,” in which each cell can have one of two values—say, “black” or “white”—and the sequence of states is determined by three simple rules, called “birth,” “death,” and
“survival.” 7 The game can produce an amazing variety of patterns. Some of them “move”; others remain stable; yet other patterns oscillate or behave in more complex manners. 8
While cellular automata were used by professional and amateur mathematicians to invent numerous games, they were also studied extensively as mathematical tools for scientific models. Because of their network structure and their ability to accommodate large numbers of discrete variables, these mathematical forms were soon recognized as an exciting alternative to differential equations for modeling complex systems. 9 In a sense, the two approaches— differential equations and cellular automata—can be seen as different mathematical frameworks corresponding to the two distinct conceptual dimensions—structure and pattern—of the theory of living systems.
Simulating Autopoietic Networks
In the early 1970s Francisco Varela realized that the step-by-step sequences of cellular automata, which are ideal for computer simulations, provided him with a powerful tool for simulating autopoietic networks. Indeed, in 1974 Varela succeeded in constructing the appropriate computer simulation together with Maturana and computer scientist Ricardo Uribe. 10 Their cellular automaton consists of a grid in which a “catalyst” and two kinds of elements move randomly and interact with one another in such a way that further elements of both kinds may be produced; others may disappear, and certain elements may bond with each other to form chains.
In the computer printouts of the grid, the “catalyst” is marked by a star (★). The first kind of element, which is present in great numbers, is called a “substrate element” and is marked by a circle (o); the second kind is called a “link” and is marked by a circle inside a square ([o]). There are three different kinds of interactions and transformations. Two substrate elements may coalesce in the presence of the catalyst to produce a link; several links may “bond”—that is, they may stick together—to form a chain; and any link, either free or bonded in a chain, may disintegrate again
197
into two substrate elements. Eventually a chain may also close upon itself.
The three interactions are defined symbolically as follows.
1. Production: * + o + o—> * + \o\
2. Bonding: § + \o\ —> \o\-{g\
M + 0 —> [0H0H0]
etc.
3. Disintegration: [o] —> 0 + 0
The exact mathematical prescriptions (the so-called algorithm) for when and how these processes take place are quite elaborate. They consist of numerous rules for the movements of the various elements and for their mutual interactions. 11 For example, the rules for motion include the following:
Substrate elements are allowed to move only into unoccupied spaces (“holes”) in the grid, while the catalyst and the links may displace substrate elements, pushing them into adjacent holes. The catalyst may similarly displace a free link.
The catalyst and the links may also exchange places with a substrate element and thus can pass freely through the substrate.
• Substrate elements, but not the catalyst or the free links, may pass through a chain to occupy a hole behind it. (This simulates the semipermeable membranes of cells.)
• Bonded links in a chain cannot move at all.
Within these rules the actual motion of the elements and many details of their mutual interactions—production, bonding, and disintegration—are chosen at random. 12 When the simulation is run on a computer, a network of interactions is generated, which involves many random choices and thus may generate many dif-
ferent sequences. The authors were able to show that some of those sequences generate stable autopoietic patterns.
An example of such a sequence from their paper, shown in
oooooooooo
oooooooooo
oooooooooo
oooooooooo
oooooooooo
oooooooooo
oooooooooo
oooooooooo
oooooooooo
oooooooooo
oooooooooo oooooooooo oo@®§ooooo oo® @000 000 * 0000 000 0000 000000 000 oooooooooo oooooooooo oooooooooo
oooooooooo
O0OO0OOOOO
00 000OOO 000 0 000
000 * 0000 0000 0000
0000000000 oooooooooo 0000000 00 oooooooooo
0000000000 o 00000000 0000000000
000 0 0000 °°| A 0000 0000000000 0000000000 oooooooooo oooooooooo oooooooooo
Table caption000000000
Table caption0000 00000 00000 0000
0000000000 | OO0 | !®0OOOOO | OO000OOOOO | |||
OO 000 € | 50000 | 00 ® | 3000 | 000000s | aooo | |
OO® 0 | 0000 | oo| | 0 OG | aooo | OO000OG | aooo |
0000*00000 | 00® | 0*0 G | aooo | OO® *®G | aooo | |
OO000S | 50000 | 00® | ©@®Hs | 0000 | OO0000S | aooo |
Table caption000000 000 oooooooooo oooooooooo oooooooooo
Stage 5
OOOOOO0OOO
oooooooooo
oooooooooo
oooooooooo
0000000000 oooooooooo oooooooooo 00 0000000
seven stages, is reproduced in figure 9-1. In the initial state (stage one) one space in the grid is occupied by the catalyst and all the others by the substrate elements. In stage two several links have been produced and, accordingly, there are now several holes in the grid. In stage three more links have been produced and some of them have bonded. The production of links and the formation of bonds both increase as the simulation proceeds through stages four to six, and in stage seven we see that the chain of bonded links has closed upon itself, enclosing the catalyst, three links, and two substrate elements. Thus the chain has formed an enclosure that is penetrable for the substrate elements but not for the catalyst. Whenever such a situation occurs, the closed chain may stabilize itself and become the boundary of an autopoietic network. Indeed, this happened in this particular sequence. Subsequent stages of the computer run showed that occasionally some links in the boundary would disintegrate, but that these would eventually be replaced by new links produced inside the enclosure in the presence of the catalyst.
In the long run the chain continued to form an enclosure for the catalyst, while its links kept disintegrating and being replaced. In this way the membrane-like chain became the boundary of a network of transformations while at the same time participating in that network of processes. In other words, an autopoietic network was simulated.
Whether or not a sequence of this simulation will generate an autopoietic pattern depends crucially on the disintegration probability that is, on how often links will disintegrate. Since the delicate balance of disintegration and repair” is based on random motion of substrate elements through the membrane, random production of new links, and random motion of those new links to the repair site, the membrane will remain stable only if all those processes are likely to be completed before further disintegrations occur. The authors showed that with very small disintegration probabilities viable autopoietic patterns can indeed be achieved. 13
Binary Networks
The cellular automaton designed by Varela and his colleagues was one of the first examples of how the self-organizing networks of living systems can be simulated. Over the past twenty years many other simulations have been studied, and it has been demonstrated that these mathematical models can spontaneously generate complex and highly ordered patterns, exhibiting some important principles of the order found in living systems.
These studies intensified when it was recognized that the newly developed techniques of dynamical systems theory—attractors, phase portraits, bifurcation diagrams, and so on—can be used as effective tools to analyze the mathematical network models. Equipped with these new techniques, scientists once more studied the binary networks developed in the 1940s and found that even though these are not autopoietic networks, their analysis leads to surprising insights about the network patterns of living systems. Much of this work has been carried out by evolutionary biologist Stuart Kauffman and his colleagues at the Santa Fe Institute in New Mexico. 14
Since the study of complex systems with the help of attractors and phase portraits is very much associated with the development of chaos theory, it was natural for Kauffman and his colleagues to ask: What is the role of chaos in living systems? We are still far from a full answer to this question, but Kauffman’s work has resulted in some very exciting ideas. To understand these, we need to take a closer look at binary networks.
A binary network consists of nodes capable of two distinct values, conventionally labeled ON and OFF. It is thus more restrictive than a cellular automaton, whose cells may take on more than two values. On the other hand, the nodes of a binary network need not be arranged in a regular grid but can be interconnected in more complex ways.
Figure 9-2
A simple binary network.
Binary networks are also called “Boolean networks” after the English mathematician George Boole, who used binary (“yes-no”) operations in the mid—nineteenth century to develop a symbolic logic known as Boolean algebra. Figure 9-2 shows a simple binary, or Boolean, network with six nodes, each connected to three neighbors, with two nodes being ON (drawn in black) and four being OFF (drawn in white).
As in a cellular automaton, the pattern of ON-OFF nodes in a binary network changes in discrete steps. The nodes are coupled to one another in such a way that the value of each node is deter-
201
mined by the prior values of neighboring nodes according to some “switching rule.” For example, for the network pictured in Figure 9-2 we may choose the following switching rule: A node will be ON at the next step if at least two of its neighbors are ON at this step, and OFF in all other cases.
