[ Figure 1 ] COMPUTER SIMULATION has made it practical to consider many new kinds of models for natural phenomena. Here the stages in the formation of a snowflake are generated by a computer program that embodies a model called a cellular automaton. According to the model, the plane is divided into a lattice of small, regular hexagonal cells. Each cell is assigned the value 0, which corresponds to water vapor (black), or the value 1, which corresponds to ice (color). Beginning with a single red cell in the center of the illustration, the simulated snowflake grows in a series of steps. At each step the subsequent value of any cell on the boundary of the snowflake depends on the total value of the six cells that surround it. If the total value is an odd number, the cell becomes ice and takes on the value 1; otherwise the cell remains vapor and keeps the value 0. The successive layers of ice formed in this way are shown as a sequence of colors ranging from red to blue every time the number of layers doubles. The calculation required for each cell is simple, but for the pattern shown more than 10,000 calculations were needed. The only practical way to generate the pattern is by computer simulation. The illustration was made with the aid of a program written by Norman H. Packard of the Institute for Advanced Study.

[ Figure 2 ] MATHEMATICAL AND COMPUTATIONAL METHODS are applied in various ways in the study of random walks. A random walk is a model for such physical processes as the Brownian motion of a small particle suspended in a liquid. The particle undergoes random deflections as it is bombarded by the molecules in the liquid; its path can thus be described as a sequence of steps, each taken in a random direction. The most direct way to deduce the consequences of the model is by a computer experiment. Many random walks are simulated on a computer and their average properties are measured. The diagram shows a histogram in which the height of each bin records the number of simulated random walks that were found to have reached a particular range of positions after a certain time step. As more trials are included, the shape of the histogram approaches that of the exact distribution of positions. For an ordinary random walk it is possible to derive the exact distribution directly. A differential equation can be constructed for the distribution, and the equation is simple enough for an exact solution to be given. For most differential equations, however, no such exact solution can be obtained, and approximations must be made. In numerical approximations the smooth variation of quantities in the differential equation is approximated by a large number of small increments. The results shown in the diagram were obtained by a computer program in which the spatial and temporal increments were small fractions of the lengths and times for individual steps in the random walk. Algebraic approximations to the differential equation are found as a series of algebraic terms. The diagram shows the first three terms in such a series. The contribution of each term is shown as a solid black line or curve. The line or curve is added by superposition to the broken black line or curve that represents the previous order in the approximation. The result of the superposition is the current order in the approximation (solid colored curves).

[ Figure 3 ] COMPUTATIONAL METHODS alone are used in the study of self-avoiding random walks. Self-avoiding random walks, which arise as models for physical processes such as the folding of polymer molecules, differ from ordinary random walks in that each step must avoid all previous steps. The complication makes it impossible to construct a simple differential equation that describes the average properties of the walk. Conventional mathematical approaches are thus ineffective. Properties of the self-avoiding random walk are found by direct simulation.

[ Figure 4 ] CHAOTIC BEHAVIOR is seen in many natural systems. A familiar example is the dripping faucet, described by a mathematical model formulated in terms of a differential equation by Robert Shaw of the Institute for Advanced Study. When the rate at which water flows through the faucet is very low, drops of equal size are formed at regular intervals (left). The model implies that if the position of the top of each drop that forms (arrows) is plotted against the mass of the drop, a simple closed curve called a limit cycle is obtained (right). The evolution of the system is represented by a point that traces the curve with time. If the flow is increased, the behavior of the system suddenly becomes more complicated. A phenomenon known as period doubling occurs, and pairs of drops, often of different sizes, are formed in each cycle. If the flow is further increased, there is a sequence of additional period doublings. Finally, just before the water flowing from the faucet becomes continuous an irregular stream of drops is produced. The drops have an entire range of sizes, and the intervals between the formation of consecutive drops appear to be random. The behavior of the system is then described by an irregular curve called a strange or chaotic attractor. The form of the curve is implied by the differential equation, but in practice it can be found only by numerical-approximation techniques.

[ Figure 5 ] MATHEMATICAL CALCULATIONS are carried out by a computer in this example of a dialogue in the SMP computer language developed by the author. The computer manipulates algebraic formulas and other symbolic constructs as well as numbers. The commands in the language include all the operations of standard mathematics. The last few panels show how new operations can be defined and then are applied by the computer to simplify any expression that includes the function.

[ Figure 6 ] CELLULAR AUTOMATA are simple models that appear to capture the essential features of a wide variety of natural systems. A one-dimensional cellular automaton is made up of a line of cells, shown in the diagram as colored squares. Each cell can take on a number of possible values, represented by different colors. The cellular automaton evolves in a series of steps, shown as a sequence of rows of squares progressing down the page. At each step the values of all the cells are updated according to a fixed rule. In the case illustrated the rule specifies the new value of a cell in terms of the sum of its previous value and the previous values of its immediate neighbors. Such rules are conveniently specified by code numbers defined as shown in the diagram; the subscript 3 is given because each cell can take on one of three possible values.

[ Figure 7 ] EXPERIMENTAL MATHEMATICS is an exploratory technique made possible largely through the use of computers. Any set of mathematical rules can be applied repeatedly by a computer and their consequences explored in an experimental fashion. For example, in order to study a pattern generated by the cellular automaton defined by the rule shown, one begins by explicitly simulating on a computer many steps in the evolution of the cellular automaton. Inspection of the pattern obtained then leads to the conjecture that it is fractal, or self-similar, in the sense that parts of it, when enlarged, have the same overall form as the whole. The conjecture, once made, is comparatively easy to prove by conventional mathematical techniques. The proof can be based on the fact that the initial conditions for growth from certain cells in the pattern are the same as the conditions for growth from the very first cell. There are an increasing number of mathematical results that were discovered in computer experiments. Some of them have subsequently been reproduced by conventional mathematical arguments.

[ Figure 8 ] COMPLEX BEHAVIOR can develop even in systems with simple components. The eight cellular automata shown in the photographs are made up of lines of cells that take on one of five possible values. The value of each cell is determined by a simple rule based on the values of its neighbors on the previous line. Each pattern is generated by the rule whose code number is given in the key (see illustration on page 197). The patterns in the upper four photographs are grown from a single colored cell. Even in this case the patterns generated can be complex, and they sometimes appear quite random. The complex patterns formed in such physical processes as the flow of a turbulent fluid may well arise from the same mechanism. Complex patterns generated by cellular automata can also serve as a source of effectively random numbers, and they can be applied to encrypt messages by converting a text into an apparently random form. The patterns in the lower four photographs begin with disordered states. Even though the values of the cells in these initial states are chosen at random, the evolution of the cellular automata gives rise to structures of four basic classes. In the two classes shown in the third row of photographs the long-term behavior of the cellular automata is comparatively simple; in the two classes shown in the bottom row it can be highly complex. The behavior of many natural systems may well conform to this classification.

[ Figure 9 ] UNDECIDABLE PROBLEMS can arise in the mathematical analysis of models of physical systems. For example, consider the problem of determining whether a pattern generated by the evolution of a cellular automaton will ever die out, so that all the cells become black. The patterns generated by the cellular automaton shown above are so complicated that the only possible general approach to the solution of the problem is to explicitly simulate the evolution of the cellular automaton. The pattern obtained from the initial state shown at the left is found to die out after just 16 steps. The initial state in the center yields a pattern that takes 1,016 steps to die out. The initial state at the right gives rise to a pattern whose fate remains unclear even after a simulation carried out over many thousands of steps. In general no finite simulation of a fixed number of steps can be guaranteed to determine the ultimate behavior of the cellular automaton. Hence the problem of whether or not a particular pattern ultimately dies out, or halts, is said to be formally undecidable. The cellular automaton shown here follows a rule specified by the code number .

[ Figure 10 ] COMPUTATIONAL IRREDUCIBILITY is a phenomenon that seems to arise in many physical and mathematical systems. The behavior of any system can be found by explicit simulation of the steps in its evolution. When the system is simple enough, however, it is always possible to find a short cut to the procedure: once the initial state of the system is given, its state at any subsequent step can be found directly from a mathematical formula. For the system shown schematically at the left, the formula merely requires that one find the remainder when the number of steps in the evolution is divided by 2. Such a system is said to be computationally reducible. For a system such as the one shown schematically at the right, however, the behavior is so complicated that in general no short-cut description of the evolution can be given. Such a system is computationally irreducible, and its evolution can effectively be determined only by the explicit simulation of each step. It seems likely that many physical and mathematical systems for which no simple description is now known are in fact computationally irreducible. Experiment, either physical or computational, is effectively the only way to study such systems.