Cellular Automata

Complex behavior resulting from collective activities of simple subunits occurs in "cellular automata." Von Neumann's (1966) original cellular automaton consisted of a large number of identical "cells" connected in a uniform pattern. The term "cell" was chosen by Von Neumann and others as the indivisible subunit in "cellular automata" based on biological "cells" as indivisible subunits of life. Much like atoms once indivisible, are now recognized to be composed of electrons, protons, neutrons, quarks, etc., it is now apparent that biological cells are complex entities whose actions depend on collective functions of intracellular structures including the cytoskeleton. Nevertheless, "cellular" in cellular automaton jargon means an indivisible grain, a discrete subunit with a finite number of states. The essential features of cellular automata are 1) at a given time, each cell is in one of a number of states. 2) The cells are organized according to a fixed geometry. 3) Each cell communicates only with other cells in its neighborhood; the size and shape of the neighborhood are the same for all cells. Depending on geometry, the number of neighbors may be 4 (rectangular), 6 (hexagonal), 8 (rectangular with corners) or more neighbors per subunit or cell. 4) There is a universal clock. Each cell may change to a new state at each tick of the clock depending on its present state, and the present states of its neighbors. The rules for changing state are called the transition rules of the cellular automata. At each clock tick (or "generation") the behavior of each cell depends only on the states of its neighbors and its own state. In cellular automaton, simple neighbor rules can lead to complex, dynamic patterns.

Cellular automaton may be considered similar to lattice models such as a two dimensional Ising generator. Based on magnetic spin states of components within a lattice, Ising generators evolve to stable patterns in which states of opposite spin align in one direction, and like spins align in another direction. A generalized two dimensional Ising generator is shown in Figure 1.11. Cellular automaton models in microtubules (Chapter 8) evolve to similar states in which opposite states align in one direction, and similar states align in another direction (Figure 1.12).

Von Neumann studied how cellular automata could perform useful computations. He assumed a large number of cells start in a quiescent, or inactive state and that input was encoded by placing a number of contiguous cells in a specific pattern. By then running the clock through a sequence of generations, an output can be obtained by the patterns of states at a later time. A cellular automaton is said to be universally computing if, for any solvable problem, there is an initial configuration of the cellular automaton which evolves to a configuration containing the solution. As far as implementing such computing capabilities, access to every cell must be established to set its initial state and read its final state. Von Neumann discovered a universally constructing cellular automaton in which an initial configuration of a small number of cells (the "constructor") can set initial states of distant cells to the pattern required to solve any problem. The constructor communicates with distant cells through intermediate cells according to transition rules. If a cellular automaton is universally constructing, it can be "programmed" to solve any problem, even if only a few cells can communicate with the outside world. Several universally constructing cellular automata have been devised in simulation; "constructors" as patterns of cytoskeletal subunit conformation would be useful mechanisms for biological computation.

1

t

4

t

4

t

4

T

4

T

4

t

4

T

4

T

4

t

4

T

4

T

4

t

4

t

4

T

i

t

4

t

4

T

4

T

4

t

4

T

X

t

4

t

4

T

4

T

4

T

¥

4

T

4.

T

4

t

4

t

4

t

y

7

4

t

i

t

i

t

4

T

4

T

4/

7

7

4

J-

t

4

t

4

t

4

T

1/

7

7

7

4

i

4

t

-i

t

4

r

4/

7

7

7

4

T

i

T

I

t

4

T

4/

X

7

7

4

t

4

t

T

4

t

4/

7

7

7

4

t

4

t

i

t

4

T

4/

7

7

4

4

t

4

t

4

T

1

f

1/

7

7

7

i

t

4

t

4

t

4

t

y

7

7

4

t

4

t

4

t

4

f

y

7

7

\

4

t

4

t

4

t

4

t

V

7

7

4

4

T

4

t

4

t

4

t

4

V

7

i

T

4

t

4

T

4

t

4

T

V

/t

4-

t

4

T

4

t

4

t

4

t

4

T

4

t

4

T

4

t

4

r

4

T

4

T

Figure 1.11 Two dimensional Ising generator evolves to stable state of opposite spin states aligned horizontally, and like spin states aligned diagonally. This stable configuration is similar to MT automaton simulation (Figure 1.12). Computer generation by Conrad Schneiker.

Cellular automata are frequent topics of Scientific American's Mathematical Games columns. Written by Martin Gardner and, more recently, A. K. Dewdney these columns have intermittently focused on the game of "Life," a cellular automaton invented by Cambridge mathematician John Conway in 1968 (Gardner, 1970). "Life" is played on a large two-dimensional grid of square cells. Each cell has eight neighbors, four at the edges and fourat the corners, and exists in one of two states: "dead" or "alive." At each generation, cells may die or come alive, their fate determined by the number of living neighbors. For example a living cell with fewer than two living neighbors, or more than three, will not survive (due to lack of sustenance or overcrowding, respectively). A dead cell will be born in a subsequent generation if it has exactly three living neighbors (or "parents"). Conway's game was named "Life" because the cells could be either dead or alive, however the behavior of the patterns of "living" cells included some "life-like" behaviors. These included movement through the grid and oscillatory patterns which came to be called blinkers, beacons, gliders, and beehives. Repeating von Neumann, though in a much simpler format, Dewdney (1985) showed that a computer could exist within the game of Life.

Figure 1.12: Cellular automaton model in microtubules (Chapter 8) reaches stable state in which opposite states are aligned along long axis of MT, and like states aligned along rows. A "kink-like" pattern is seen moving through the structure. By Paul Jablonka.

Carter Bays has extended the game of "Life" to three dimensions (Dewdney, 1987). In his version, each cell is a cube with 26 neighbors, but the neighbor rules are essentially the same as in Conway's two-dimensional "Life." A variety of interesting behaviors ensue in Bay's "Life," dependent on initial patterns. For example he observed a 10 cube "glider" traveling through space like a "sofa in free fall." Another 7 cube form (a "greeter") dies unless it is in the presence of another structure. Gliders which pass near greeters are grabbed and held until rescued by a second glider which collides with the repressive greeter. Other stable patterns emerge which Bays has called arcades, stairs, helices, and space-time barriers. Life and other cellular automata have enraptured computer buffs who can now create their own realms. Beyond that, cellular automata have serious scientific and mathematical implications.

Stephen Wolfram (1984) has viewed cellular automata as systems of simple components capable of complex collective effects such as the simulation of partial differential equations and deterministic chaos. He has described four general behaviors for cellular automata patterns. 1) They disappear with time, 2) they evolve to a fixed finite size, 3) they grow indefinitely at a fixed speed, 4) they grow and contract irregularly. Type three, which grow indefinitely at a fixed speed, are often found to be self similar in scale; parts of such patterns when magnified are indistinguishable from the whole. Thus these cellular automata patterns are characterized by a fractal dimension.

Wolfram notes that the mechanisms for information processing in natural systems appear more similar to those in cellular automata which are highly parallel than to conventional serial processing computers. The "results" are given by the configuration obtained; the "medium is the message." Further, "it is common in nature to find systems whose complexity is generated by the cooperative effect of many simple identical components." Cellular automata are sensitive to initial conditions and their behavior is characterized by the stability or predictability of their behavior under small perturbations in initial configurations. With a given set of rules, changes in a single initial site value can lead to markedly different patterns. Such perturbations have characteristic effects on Wolfram's four classes of cellular automata: 1) no change in final state, 2) changes only in a finite region, 3) changes over an ever increasing region, 4) irregular change. Thus at least some cellular automata patterns are nonlinear and deterministic.

Figure 1.13: Self replicating automata described by Edward Fredkin (Dewdney, 1985). "Off" states are shown as all black. Computer generation by Conrad Schneiker.
Figure 1.14: Self replicating automata described by Edward Fredkin (Dewdney, 1985). Computer generation by Conrad Schneiker.

Cellular automata can be ascribed to exist within a variety of environments. Perhaps the most extreme view is that the universe is a cellular automaton. MIT's Edward Fredkin has been contending that the universe may work according to the same principles as a cellular automaton (Wright, 1985). He believes the basic material of which everything is made of can be considered as information rather than mass and energy. Working at the interface of physics and computer science, Fredkin has become intrigued with the relations between cellular automata and nature. With the right rules, a cellular automaton can simulate the formation of a snowflake, mollusc shell, or galaxy. Fredkin's view is to apply cellular automata to fundamental levels of physics and the rules needed to model the motion of molecules, atoms, electrons, and quarks. With sufficient information to model these particles, an automaton may be designed that describes the physical world with perfect precision. At that level, says Fredkin, the universe is a cellular automatonin three dimensions: a lattice of interacting logic units, each one deciding billions of times per second whether it will be "off or on" at the next instant. Fredkin sees this information as the fabric of reality, the stuff from which matter and energy are made. He argues that cellular automata can represent the universe as usefully as can differential equations, the prevalent mathematical alternative. The cellular automaton view is by far the simpler. A child can understand the rules governing a cellular automaton and with pencil, paper and enough time can predict the course of an automaton including charting the growth of a snowflake, the ripples of a pond or a sound wave. Cellular automata are the language of pure information and may be involved in biological information processing as well as future computer devices. Forrest Carter (1984) of the Naval Research Lab and James Milch (1986) of Eastman Kodak have both proposed the construction of molecular automata, extolling the virtues of the cellular automaton concept applied to problems of interfacing to molecular scale devices. With a large cellular automaton molecular computer, communication to the "macro" world need only interface with a "constructor," a small portion which can take advantage of the entire cellular automaton capacity.

Subunits of cytoskeletal microtubules may be particularly suitable for "cellular" automaton behavior and information processing in the nanoscale. Cytoskeletal automata and their dynamic consequences may be an important substrate of biological computing ranging from the actions of single cells to brain/mind consciousness. Will they pave the way to Ultimate Computing?

0 0

Post a comment