next up previous contents
Next: Periods in time Up: Cycles in space Previous: The evolution matrix

The reduced evolution matrix


The matrices are rectangular rather than square because of the incomplete neighborhoods at the ends of a chain of finite length, which preclude calculating the evolution of all the cells of the chain. This incompleteness was fully understood in defining such matrices, but it would still be useful if the evolution of a block of cells could be related to the block itself. One approach would be to close the block into a ring. Variations on the same theme would involve extending the block in various ways before closing it into a ring, somewhat in the way that a Möbius strip is formed by giving a strip of paper a twist before joining its ends to form a cylinder.

Another approach to compensating the lack of knowledge of what lies beyond the limits of a finite chain would be to characterize the possible extensions of the chain numerically and either storing this information in a square matrix, or possibly annotating the links of a connectivity diagram.

For example, let the rows of the matrix be indexed by the sequences of N bits, and the columns by the central sequences of N+2 bits which can evolve into their indices via one of the (2,1) rules. The number of counterimages of each row index can range from zero to four, and this number could be recorded as the matrix element. Let us call such a matrix a reduced evolution matrix, denoted by . Then

For example, choose N=3, and use Rule 22; then,

The column sums are always 4, but the row sums could range between 0 and 32, according to the rule involved. A zero sum would signify a Garden of Eden state, because the row index would then have no chains from which it could be formed. The high extreme would signify a pathological rule favoring one single sequence, for example Rule 0 mapping all chains into the zero chain. Diagonal elements do not portend chains of period one, but a still life could not exist if all diagonal elements were zero.

Unfortunately the square of E does not correspond to the number of two-generation ancestors producing a given chain even though it arises from two steps of evolution. The reason is precisely the correlations introduced by the order in which cells occur. Squaring E implies some ancestor for each step of the evolution, but does not guarantee that they coincide where they overlap. An easy counterexample is obtained from chains of length 1. for rule 22 is

so its square is

The table for two generation evolution according to Rule 22 is

which produces a two-generation reduced evolution matrix

which is clearly different from the square of the one-generation matrix.

There is an evident relation between the evolution matrices and the reduced evolution matrices ; If we define a matrix R, for which

is typical, we have

and the evident definition

In such terms it is clear that as a general proposition.

next up previous contents
Next: Periods in time Up: Cycles in space Previous: The evolution matrix

Harold V. McIntosh