Cellular Automata and Recursive Growth

19.1 An Analog and Digital World

When we stroll across the quadrangle on a university campus, we feel we move through unbroken space that smoothly connects our beginning and ending points and that time flows continuously without interruption during our walk. When we pour water from one container to another, it is a continuous stream of water that flows. Yet, we know that water, at one level, is composed of discrete molecules. And we know that organisms reproduce discretely; each female produces an integer number of offspring or each asexually dividing cell results in exactly two cells. In the space and time scales of human movement, we are a distinct entity that moves, not an amorphous, diffuse, electromagnetic field. Moreover, our neurons fire at discrete intervals, with finite recovery periods, and, more or less, in an on-off manner that prevents our observing the world at arbitrarily small time intervals. In this way, our senses and perceptions are digital; it is something else that makes us think reality is continuous. It could be reality itself that gives us this idea, even if we base our beliefs on incomplete knowledge. Indeed, many of our earlier models and techniques used a discrete representation that was justified as an abstraction to simplify our computations or analysis of what we believed to be the true, underlying continuous physical reality. But given the particulate nature of our perceptions of nature and the underlying discreteness of many biological processes, we have to ask: Which is the reality and which the abstraction: continuous or discrete - analog or digital? Given that the world includes the observers and that, to a certain extent, the world is as we observe it, the answer is probably "both."

Other chapters (e.g., Chapters 5 and 16) describe biological processes with spatial extent. Systems that are viewed as occupying space invite a discrete representation. Even when we use continuous mathematics such as PDEs to describe movements from place to place, to solve the equations we discretize space and time. Space becomes a grid of discrete points at which events occur. Moreover, not every model concerns a dynamical system; we also wish to model systems such as biological shapes or

ad, abcdabc, adadbcbcdabc,...

ad, abcdabc, adadbcbcdabc,...

Figure 19.1: Two state transition diagrams, (a) A three-state determinant FSA and a sample of the output language, (b) A three-state indeterminant FSA and a sample of its output.

organism morphology and anatomy. These too can be usefully represented as discrete: a plant is composed of discrete modules such as branches, nodes, leaves, etc. In this approach, we model an individual plant as a repetitive collection of these basic discrete building blocks. In this chapter, we will describe several disparate approaches and tools for the discrete perspective of biological modeling. One of the central concepts for this perspective is finite state automata, a mathematical object used extensively in theoretical computer science.

The systems and models we present in this chapter address some fundamental biological questions. (1) Does the spatial position of individual plants affect populationlevel phenomena such as species coexistence? (2) What are the causes of heart failure? (3) What biological forces are necessary to explain the broad patterns of plant evolution? All of these questions share the characteristic that discrete, recursive structures can be used to answer them.

19.2 Finite State Automata

Finite state automata (FSAs) are a family of mathematical constructs that, informally speaking, are defined by a finite set of states, an output alphabet, and rules that take the automaton from its current state to the next state. [This definition is a simplification, and the reader should consult Arbib 1965 or Hopcroft and Ullman 1969 for embellishment.] One of the states is designated the initial state from which the execution of the FSA begins.

When the machine changes state it produces a symbol; the dynamics of the machine are reflected in the sequence of symbols that it produces. The symbol might simply represent the last state of the machine, but there is no necessary connection between the value of the state and the symbol produced. Figure 19.1a shows a FSA that has three states and that produces either a, b, or c at the indicated state transition. The set of sequences of symbols can be considered to be the language that the FSA produces, and the state transition rules constitute the grammar that underlies the language.

A FSA can be either determinant (Fig. 19.1a) or indeterminant (Fig. 19.1b). A determinant FSA is one in which the state transition rules are such that each state goes from one state to only one other state. An indeterminant FSA has at least one state that can become one of several possible states. In this case, the transition rules must have a mechanism for choosing one of the alternatives. This is usually done randomly. Rules

Figure 19.2: FSA transition rules stated as a table (a) for a determinant FSA, where rows are the current states; columns are the subsequent state, and table elements are the output symbols, and as probabilistic rules (b), where —> S2(by, p = 0.5 means "change state 1 to state 2 and output b with probability 0.5."

can be stated as a look-up table or as an equation in which the next state is computed from the current one (Fig. 19.2).

19.3 Cellular Automata

A cellular automaton (CA) is a spatially explicit form of a FSA. A set of cells are defined in a space; each cell is a FSA whose transition function depends on the cell's own state and those of neighboring cells. Typically, the symbolic output of CAs is the state of each cell. Later, we will discuss L-systems, which are another special case of a C A-like construct that has symbolic output used to describe the growth of biological structures (e.g., plants).

Consider the following simple example. We define the space to be a one-dimensional sequence of squares. Each square represents a FSA that has two states (0, 1), and the transition rules depend only on the immediate left and right neighbors of cell. The transition rule is very easy to state verbally: if the middle cell is in state 0 and has exactly one neighbor in state 1, the middle cell state changes to 1. Otherwise, the state becomes (or remains) 0. Figure 19.3 shows the spatial pattern (horizontal) that develops over time (vertical) when the rules are applied to each cell in the space. Recall that all changes in state are done "in parallel," so that the previous state of neighbors is used, not that resulting from the current changes.

CAs can be defined over a space with any number of dimensions and with any geometrical relationships between neighbors. Typical applications use two dimensions and define the cells on a rectangular lattice. Other lattice arrangements are possible, for example, equilateral triangles and hexagons. The number of neighbors to use can be made a property of the model in two senses. First, the model must specify if diagonal neighbors are to be included. Thus, in a rectangular grid there may be four or eight contiguous neighbors, depending on the definition. Hexagonal grids do not have this problem, but triangular grids do. Second, the model must specify if non-contiguous "neighbors" are to influence the transition functions.

In real CAs coded in computers, the size of the lattice is finite, and this creates the problem of dealing with the ends of the lattice. The last cell at each end is missing one of its neighbors (Fig. 19.3b). This is the same problem as boundary conditions in PDEs. The possible solutions include (1) make a buffer (i.e., an edge of one cell around the edge of the lattice) that has a fixed state, (2) create a special rule for the edge

Was this article helpful?

0 0

Post a comment