next up previous contents
Next: Periods Up: What to look Previous: General characteristics

Cycles

There are two ways to obtain the cycles for a given automaton. The first is to enumerate all the rings of the desired length, and follow up the evolution of each. In doing so various shortcuts can be taken, such as generating the configurations in Gray code order so that only a single cell changes state from one to the next. Still lifes can be detected very quickly this way. Numerical comparison of successive generations means that whenever the new generation is smaller, it will already have been examined and need not be pursued further.

The second way is more systematic and is worth the bookkeeping effort involved. A graph whose links are determined by evolution is prepared, following which a path enumerating procedure is followed to locate all the loops, whose lengths will give the periods of all the cycles of that length. Cycles of length up to ten can be obtained easily, twenty with effort, but passing thirty requires dedication; for binary automata it is slightly easier, increasingly more difficult for others.

Certain theoretical conclusions do not depend on practical limitations. For example, we might select an initial ring and examine successive generations of its evolution. The new generations can all be distinct, or at some point we might find that an earlier generation has repeated itself. For a finite ring the first possibility cannot occur, because there are only possible different combinations of states in a ring of length n -- 32 in a binary ring of length 5, for example. If no repetitions were allowed, the supply of distinct rings would eventually be used up, so repetition is the only alternative. In practice, the number of generations elapsing before one of them repeats may be fairly large, but is usually much smaller than the exponential bound of the worst possible case.

Once repetition has occurred, we need to recall that evolution is uniquely defined -- there is just one successor to a given ring in each new generation -- so the tail end of the evolution has to repeat over and over again in a fixed cycle, starting with the generation which first repeated.

Statistics of interest concerning the cycles include: the number of cycles and their lengths, the height of the transient trees leading into the cycles, and the convergence factor at each node of these trees.



next up previous contents
Next: Periods Up: What to look Previous: General characteristics



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx