12—
On Recursively Defined Geometrical Objects and Patterns of Growth:
With R. G. Schrandt (LA-3762, August 15, 1967)

This report formed a foundation of a now great ongoing effort involving many authors concerning the behavior and growth of cellular automata. See, for instance, the proceedings of a March 1983 Los Alamos National Laboratory conference on cellular automata and reports written by Wolfram and others. This report was reprinted in Essays on Cellular Automata edited by A. Burks, published by the University of Illinois Press in 1970. (Author's note). *

Abstract

Illustrations are given of computer-generated patterns exhibited by figures "growing" according to certain recursive rules. Examples of growing patterns in twoand three-dimensional space are given. Patterns are discussed in an infinite strip of a given width where periodic growth is observed. When modification of the rules of growth allows portions of the pattern to die out, configurations split into separate connected pieces, exhibiting the phenomena of both motion and some self-reproduction. A simple conflict rule together

* Also in Science, Computers, and People, by S. Ulam, Birkhauser, 1986. (Eds.)

with this modification allows a game of survival between two systems growing in a finite portion of the plane. The examples show both the complexity and richness of forms obtained from starting with a simple geometrical element and the application of a simple recursive rule.

In this report we discuss briefly some empirical results obtained by experiments on computing machines. We continue the work described in a paper "On Some Mathematical Problems Connected With Patterns of Growth."'

Rules of Growth

Growth is in the plane subdivided into regular squares. The starting configuration may be any arbitrary set of (closed) squares. The growth proceeds by generations in discrete intervals of time. Only the squares of the last generation are "alive" and able to give rise to new squares. Given the nth generation, we define the (n + 1)th as follows: A square of the next generation is formed if

a) it is contiguous to one and only one square of the current generation, and b) it touches no other previously occupied square except if the square should be its "grandparent." In addition: c) of this set of prospective squares of the (n + 1)th generation satisfying the previous condition, we eliminate all squares that would touch each other. However, squares that have the same parent are allowed to touch.

In three dimensions the growth rules are the same. One merely replaces the squares by cubes and observes all three provisions.

We show an example of such a pattern growing on the infinite plane and then discuss patterns of growth in an infinite strip of a given width where a periodic growth is observed. We discuss, beyond the work mentioned in Ref.1, the behavior of figures growing according to our rules, with a new proviso: every element of the figure which is older than a specified number of generations, say two or three, "dies," i.e., is erased. This makes the figure move in the plane. We show some cases of such motion, with occasional splitting of the figures into separate connected pieces. In some cases these figures are similar to

the original ones, thus exhibiting phenomena of both motion and of self-reproduction. As another amusement we tried on the computers the following game: starting, still in the plane with two separate initial elements, we let each grow according to our rule (including erasure or death of the "old" pieces); then when the two patterns approach each other we still apply the rule of a further growth of each figure with the proviso that the would-be grown new pieces are not put in if they should try to occupy the same square. This gives rise to a game for survival or a "fight" between two such systems-in some cases both figures die out.

Finally, we give an example of a similar process of growth in threedimensional space (subdivided into regular cubes) with our rules for recursive addition of new elements.

Two-Dimensional Patterns

We present as examples of the planar type of pattern Figs. la and lb. Our start was a single square. The patterns are plotted merely in one quadrant of the plane and show the result of 100 and 120 generations of growth, respectively. Fig. lb shows the pattern on a large square with 100 units on a side; the portion of growth that extends beyond 100 units horizontally or vertically is not plotted. The figures are symmetric about the diagonal of the square, and the density of the occupied squares is about 0.44. There is no apparent periodicity in portions of this pattern. As shown in Ref. 1, the "stems" grow indefinitely on the sides of the quadrant, and the side branches split off from the stem. It is not known whether some of these side branches will grow to infinite length or whether they will all in turn be choked off by other side branches growing from the stem at later times.

In Fig. 2 we show a pattern grown from an initial configuration consisting of three noncontiguous squares at the vertices of an approximately equilateral triangle. One will note that the patterns in the subquadrants are both identical to those of Figs. la and lb. The borders or strips between the subquadrants are due to interference between patterns generated by the individual starting squares. One of the strips reduces to a stem, since two of the starting squares generate patterns symmetric with respect to a 45^° line through the center of the triangle.

By restricting in advance the growth of a pattern to an infinite strip of finite width in the plane, one observes a periodic growth. The

proof that in a finite strip the pattern must be periodic is easily obtained. On inspection of our growth procedure one observes that the last generation is confined to a part of the strip which extends through its width and an equal distance in length back of the most forward square. There is only a finite number of possible patterns in such a square. Therefore, a configuration must repeat itself and from then on the whole process starts again. Figure 3 shows different patterns generated in strips of widths from 8 to 15 through 100 generations of growth. In each case the start is a single square in the upper left-hand corner of the strip. Table I gives the observed lengths of the periods for strips of widths 1 to 17. There seems to be no simple relation between the width of the strip and the length of the period.

Rules for Termination or "Death" in the Pattern

We have experimented with a rule for erasing, i.e., elimination of a part of the pattern after it is a fixed number of generations old. For this we have adopted a simpler rule of growth of the pattern by assuming only condition (a). Each square that is a certain fixed number k of generations old is erased or "dies" and becomes unoccupied. Later on, the pattern may grow back into these unoccupied positions. We took for k either the values 1, 2, or 3. For example, given a pattern, we grow the squares of the (n + 1)th generation from those of the nth, and then erase those of the (n-1)th. Under this rule the pattern will move and it may split up into disconnected pieces, as shown in Fig. 4a. It turns out that certain parts of the pattern replicate themselves in shape, and these repeat as subpatterns. One such subpattern consists of a straight strip of squares with two additional squares on each end. We call this rather frequent replication subpattern a "dog bone." (See Fig. 4b.)

Another construction concerns the behavior of such patterns in a finite portion of the plane. We have adopted a large square as the space for growth. Its boundary acted as an absorber so that each square which would possibly grow from a square on the boundary was not considered. This was studied under the simplified rule of growth mentioned above. Starting with an initial configuration, say a single small square, the pattern will grow and either eventually "die," or else will become periodic in time and continue indefinitely. In most cases the pattern eventually disappears or dies. This is because the death rule eliminates the old squares, and the simple conflict rule together with the boundary condition prevent any new squares from forming. For these problems we kept only the current generation, so k = 1. By

this we mean that given a configuration, we produce the next one and then immediately erase the starting one. We have run a number of cases on a computer to ascertain either the period and its length, or the number of generations before the pattern terminates. This we have done in various sizes of the large square in which the game takes place. A sampling was obtained for sizes of the large square for 2x2 up to 8x8.

As an example, consider the square of size 6x6. There are, of course, 236 possible initial configurations. Out of these we have chosen 132 such configurations at random, assuming that each of the 36 squares has 1/2 chance of being occupied initially. Each of these different starting configurations grew until it became periodic or died out. Let s be the number of states in each sequence and t the length of a period. The values of s ranged from 11 to 109 with an average of 33. The values of t were 1, 4, 6, 8, 12, and 24. Here t = 1 means the pattern died out. In our sample, 87 of the 132 cases had t = 1. The longest sequence has s = 109, with t = 24. In another experiment we tried 15 random starting configurations chosen in an 8x8 large square. The values of s ranged from 49 to 397, with t values of 1, 8, 12, and 16. Ten of our 15 experiments had t = 1.

We can formulate condition (a) of the rules of growth in another way if we keep only one generation before death. In this case the status of any square in the (n+ 1)th generation is determined only by the state of its four neighboring squares in the nth generation. Let us assign a I to an occupied square and a 0 to an empty one. We use the two operators (.) and (+), with the (+) modulo 2-that is, 1+1 = 0.

If an, bn, cn, dn are the four neighbors of a square Xn and all four symbols have values 1 or 0, that is, they represent the states of the squares in the nth generation, then the state of the square x in the next generation is simply Xn+l = -Cndn.(an +bn)+ an bn(cn + dn) where the bars above the symbols represent the complement (also modulo 2).

If the whole region in which the game is played is bounded, say, again by a large square, we will assume that the values on the boundary are always 0. The state of the configuration at time (n + 1) is then obtainable by a fixed transformation from the state at time (n).

One of the interesting properties to determine is the existence of states which are self-replicating, that is, they reproduce themselves immediately. These are the fixed points of the transformation defined above. It is easily verified that there are none such (except those identically 0, which means the pattern dies out) for squares of size 2x2 and 3x3. There exists just one such state for the 4x4 square. This is given by

For the 5x5 square there are these two:

There are none of the 6x6 case. Here is an example of one for the 17x17 case. Let A be the second of the two 5x5 matrices. Let Nc and Nr be 5x1 and 1x5 matrices, respectively, with zero elements. Then the matrix A Nc A Nc A Nr O Nr O Nr A N A Nc A Nr O Nr O Nr A N, A NC A is self-replicating.

Contests or Fights between Two Configurations

We may start, on a large finite square, with two different initial configurations each labeled, say, by a different color, so as to distinguish one set from the other. We let each grow according to condition a) of the rules of growth, plus the death rule. Now condition a) states that a square of the next generation is not formed if it is contiguous to two or more squares of the current generation. Two such squares of the current generation may be members of the same configuration or else one from each of the two different configurations. So the growth of these patterns is subject to restrictions for elements of the new generation within themselves separately, and when they are almost in

contact, with the two taken together. One or both of these systems may then go to zero or one may survive, for some time or indefinitely.

Figures 5a, 5b, 5c, 5d illustrate one case of such a fight between two starting patterns in a 23x23 square. They show the situation at generations 16, 25, 32, and 33, respectively. We kept two generations before erasure for both patterns. We assumed as initial conditions for pattern A one square in the extreme lower left-hand corner and for pattern B one square placed one unit of distance off from the upper right-hand corner. After 33 generations (Fig. 5d) pattern B won, at which time the nth generation squares of pattern A were completely erased. (The (n- 1)t generation squares of A will disappear the next generation.)

In another game we have started with two single squares in the same relative positions from the corners. For pattern A we kept one generation before erasure, and for pattern B two generations. In this case A won in 112 generations on the 23x23 board. There is no figure for this contest.

Three-Dimensional Model

We again used all three conditions of the rules of growth in forming a three-dimensional pattern. Figures 6a and 6b show two views of a model of such a pattern. Two-dimensional plots of the pattern were obtained from the computer after 30 generations of growth. The model was constructed from these plots and then photographed. The starting configuration was the single cube on the extreme left of Fig. 6a. This model represents the part grown in one octant of the space. In each octant there is a further threefold symmetry along the coordinate axes, of which we took the part x > y, x > z. There still remains a plane of symmetry at 450 to the x axis. The dark cubes represent the ₃₀th generation elements.

Our examples show both the complexity and the richness of forms obtained from starting with a simple geometrical element and the application of a simple recursive rule. The amount of "information" contained in these objects is therefore quite small, despite their apparent complexity and unpredictability.

If one wanted to define a process of growth which is continuous rather than by discrete steps, the formulation would have to involve functional equations concerning partial derivatives.

It appears to us that a general study of the geometry of objects defined by recursions and iterative procedures deserves a general studythey produce a variety of sets different from those defined by explicit algebraic or analytical expressions or by the usual differential equations.

TABLE I Width of StripPeriod of Pattern

Acknowledgments

The three-dimensional model was constructed by Barbara C. Powell and photographed by W. H. Regan.

Reference

1. S. Ulam in Proceedings of Symposia in Applied Mathematics, XIV, American Mathematical Society 1964, p. 215 to 224; see also J. C. Holladay, and S. Ulam, Notices of the American Mathematical Soc. 7 (1960), p. 234; and R. G. Schrandt, and S.Ulam, Notices of the American Mathematical Society 7 (1960), p. 642.

Fig. la. Growth from a single starting square after 100 generations.

Fig. lb. Same as Fig. la but after 120 generations.

Fig. 2. Growth from three noncontiguous starting squares.

Fig. 3. Patterns generated in an infinite strip of widths 8 to 15, after 100 generations.

Fig. 4a. Growth from a single starting square with death rule, keeping two generations. The nth generation squares are cross hatched, the (n - l)th are blank. The integers at the top are the number of squares in the n^th and (n - )th generation, and the generation number.

Fig.4b. Same as Fig. 4a but after 45 generations.

Fig. 5a. Fight between two different patterns after 16 generations, keeping two generations before erasure. There are 26 (n - 1)th generation squares of the lower pattern, and 4 nth generation squares. The upper pattern has 32 (n - )th generation squares, and 12 nth generation squares.

Fig. 5b. Same as Fig. 5a but after 25 generations.

Fig.5c. Same as Fig. 5a but after 32 generations.

Fig.5d. Same as Fig. 5a but after 33 generations. Lower pattern has been eliminated.

Fig. 6. Model of three-dimensional pattern after 30 generations of growth. The starting configuration is the single cube on the extreme right.