Printer Friendly

Faster methods for identifying nontrivial energy conservation functions for cellular automata.

1 Preliminaries: basic definitions

We consider cellular automata with k states in n dimensions. The neighborhood of a cellular automaton is the region of surrounding cells used to determine the next state of a given cell. The window of an energy function for a cellular automaton is the region of adjacent cells that contribute to the function. Both neighborhoods and windows are n-dimensional tensors, with the size of each dimension specified as a positive integer. Given the size of such a tensor, it is useful to define the following 3 sets of tensors.

Definition 1.1. Cellular automata are composed of cells, each of which is in one of k states (or colors) at any given time. The set C is the set of such colors, and the set [C.sub.*] is that set augmented with another color named *. (* denotes a special state with certain properties that simplify our proofs. It is explained in more detail in the pages that follow.)

C = {0,1, 2, ... ,k - 1} (1.1)

[C.sub.*] = C [union] {*} (1.2)

It is sometimes useful to choose one color to be treated specially. In all such cases, the color 0 will be chosen.

Definition 1.2. An n-dimensional cellular automaton rule is a function R that gives the color of a given cell on the next time step as a function of a neighborhood of cells centered on that cell on the current time step. The neighborhood is an n-dimensional tensor of size [w.sub.1] x xxx x [w.sub.n], where each [w.sub.i] is an odd, positive integer.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (l.3)

Definition 1.3. An n-dimensional cellular automaton is an n-dimensional tensor whose elements are in C, and which is updated on each time step according to a cellular automaton rule R, applied to every cell in parallel. The rule is a function applied to each cell and its neighbors, where neighbors wrap toroidally (i.e. the top edge is considered adjacent to the bottom, the left edge is adjacent to the right, and so on for each dimension).

Definition 1.4. The successor function advances a region within a cellular automaton one time step by applying a rule R to a region M of size [s.sub.1] x xxx x [s.sub.n]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which is defined as:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.4)

Note that T(R, M) is defined for an M that is only a portion of the cells, and so it does not wrap around toroidally. Instead, it returns a tensor that is smaller than M in each dimension. Also note that the ellipses on the right side of the equation are used in two different ways. Each element of the result comes from applying the R function to only a portion of the M tensor, which includes those elements of M whose first coordinate is in the range [[i.sub.1], [i.sub.1] + [w.sub.1] - 1], and whose second coordinate is in the range [[i.sub.2], [i.sub.2] + [w.sub.2] - 1], and so on up to the nth coordinate being in the range [[i.sub.n], [i.sub.n] + [w.sub.n] - 1].

Definition 1.5. A linear additive energy function (or energy function) is a function f : [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] that assigns a real number to a window of size [s.sub.1] x xxx x [s.sub.n] within a cellular automaton.

Definition 1.6. The total energy [e.sub.tot] : [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] of a given state U of an entire cellular automaton universe with [u.sub.1] x xxx x [u.sub.n] cells, with respect to a given energy function f, is

[e.sub.tot](U) = [[SIGMA].sub.W]f([U.sub.W]) (1.5)

where U is the universe state for a cellular automaton, W is the position of the energy window within that universe, and [U.sub.W] is that window within the universe, which wraps toroidally at the edges of the universe.

Definition 1.7. A conserved linear additive energy function (or a conserved function) for a given cellular automaton rule is an energy function that for a universe of any size, and for any given state of that universe, will assign the same total energy to that universe for both that state and its successor.

Definition 1.8. A trivial conserved linear additive energy function (or a trivial) is an energy function that for a universe of any size, will assign the same total energy to that universe regardless of its state. A nontrivial conserved linear additive energy function (or a nontrivial) for a given cellular automaton rule is a conserved energy function that is not trivial.

Definition 1.9. Given n positive integers [s.sub.1], ... ,[s.sub.n] defining the size of an n-dimensional tensor, the set B([s.sub.1], ... ,[s.sub.n]) is the set of all tensors over C of that size. This set is partitioned into two sets, Z([s.sub.1], ... ,[s.sub.n]), the zero-sided tensors, which have at least one side that contains the origin element and is filled entirely with zero elements, and [??]([s.sub.1], ... ,[s.sub.n]), the non-zero-sided tensors, which do not have such a side. The origin element is the element of the tensor at location (1,1, ... , 1).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.7)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.8)

So in 1 dimension, the zero-sided vectors are those whose with a 0 as the first element. In 2 dimensions, the zero-sided matrices are those with a top row of all zeros, or a leftmost column of all zeros, or both.

It is useful to define a matching function H that can be used in the construction of various functions over these tensors. The function returns 1 iff two tensors have elements that match, where the * symbol is treated as matching any color.

Definition 1.10. Given n-dimensional tensors over [C.sub.*], the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] {0,1} isdefinedas

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.9)

Given an n-dimensional tensor, it is useful to unwrap it into a 1D string of characters. This will be done in row major order. For matrices, this means the elements will be read from left to right across the top row, then left to right across the second row, and so on down to the bottom row. Tensors of other dimensionalities are unwrapped similarly, with the last dimension changing most quickly, and the first dimension changing most slowly. It is useful to have a function [V.sub.num] (T) that unwraps the elements of tensor T, then converts the resulting string to an integer by treating it as a number in base c, with the first element being the most significant digit, and the last being the least significant.

Definition 1.11. An n-dimensional tensor A with elements in C can be converted to an integer by the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], which treats the elements of the tensor as digits base k, where the elements are taken in row major order, treating the first as the least significant digit, and the last as the most significant.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.10)

For this definition, the rightmost product is understood to be 1 for all cases where the lower bound exceeds the upper.

Definition 1.12. An n-dimensional tensor with elements in C can be converted to a binary vector by the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], which is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.11)

The vector [V.sub.t](M) has one element for each possible color pattern for a tensor of the same size as M. That vector will be all zeros, except for a 1 in the position corresponding to the pattern M.

Definition 1.13. A function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] can be converted to a real vector with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] elements by the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], which is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.12)

This vector is a convenient way to represent an energy function. It completely specifies the energy function, by listing the output of the function for every possible input. We will define various classes of energy functions by simultaneous linear equations, treating the elements of this vector as the variables.

Note that the energy function window is independent of the CA neighborhood. Energy functions can be defined over regions different from the scope of the transition rule of the CA. Our work with 1D CAs in [1], for example, has identified conserved energy functions with windows of size 1 x 5, 1 x 6 and larger, for CAs that have neighborhoods of size 1 x 3.

Definition 1.14. Given tensor M of size [m.sub.1] x xxx x [m.sub.n], which is a region within an n-dimensional universe, and given an energy window size of s = ([s.sub.1],..., [s.sub.n]), a vector representing the total energy of all energy windows that fit within M can be found with the function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.13)

The e(s, M) function slides the energy window to all possible positions that fit entirely within the matrix M, and finds the energy at each position. It then sums all the energies coming from identical patterns, and constructs a vector with the total energy derived from each possible pattern. The sum of the elements of this vector would simply be the total energy of M. But it is useful to maintain the vector of separate values when generating sets of linear equations that define the trivials, the nontrivials, or the conserved functions.

Definition 1.15. For a positive integer n, the function N : [Z.sup.n] [right arrow] Z is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.14)

where [b.sub.i] is the ith bit of integer b written in binary, with bit 1 being least significant and bit n being most.

In 1 and 2 dimensions this reduces to:

N (c) = [k.sup.c-1] (1.15)

N(r, c) = [k.sup.(r-1)c] + [k.sup.r(c-1)] - [k.sup.(r-1)(c-1)] (1.16)

It will be proved below that this gives the cardinality of many of the sets that will be considered here. It equals the number of zero-sided tensors of a given size, the number of trivials, and the number of unit complements. And when subtracted from a simple power of 2, it yields the number of non-zero-sided tensors, the number of equations defining the conserved functions, and the number of equations defining the nontrivials. These terms are defined and the counts proved below.

Definition 1.16. In n dimensions, the seven transforms that operate on tensors of size [s.sub.1] x xxx x [s.sub.n]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.17)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.18)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.19)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.20)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.21)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.22)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.23)

are defined to be:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.24)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.25)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.26)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.27)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.28)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.29)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.30)

The function [P.sub.rot](d, M) rotates the elements of tensor M along dimension d, so that one side that included the origin moves to the opposite side. The function [P.sub.C] sets the central element to zero. The function [P.sub.L] transforms a zero-sided tensor by replacing the 0 elements on each all-zero side with * elements. And [P.sub.R] does the same, then rotates it so each modified side moves to the opposite side. The functions [P.sub.*], [P.sub.LD], and [P.sub.RD] are only used here to define the other functions, and won't be used again.

The following gives three examples of [P.sub.L] and [P.sub.R] applied to zero-sided matrices of size 3 x 5. In each example, M is a zero-sided matrix, where the all-zero side is on the left, top, and both, respectively:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.31)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.32)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.33)

Definition 1.17. The function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] takes a small n-dimensional tensor and pads it with zero elements on many of its sides to create a large n-dimensional tensor. In each dimension, if the small tensor was of size [s.sub.i] in that dimension, then the large tensor will be of size 2[s.sub.i] - 1 in that dimension. The zero elements are added in such a way that the last nonzero element in the original tensor becomes the center element in the new tensor.

For example,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.34)

In this 2D example, the small matrix M is of size 3x5, and [P.sub.Z] (M) is of size (2*3-1) x (2*5-1) = 5x9. Note that this M happens to have 4 nonzero elements, arranged in a sort of V shape. If the elements of M are read in row major order (i.e. left to right across the top row, then left to right on the second row, etc.), then the last nonzero element to be read is the bottom of the V. The [P.sub.Z] function pads with zeros in such a way as to yield a large matrix of the correct size, with that last nonzero element in the exact center of the large matrix.

Definition 1.18. For a given tensor size [s.sub.1] x xxx x [s.sub.n], the set T is defined to be the following set of functions

T([s.sub.1], ..., [s.sub.n]) = {[f.sub.M] | M [member of] Z([s.sub.1] x xxx x [s.sub.n])} (1.35)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1.36)

2 Theoretical results

Proofs of the theorems below are provided in a separate appendix available from the authors.

Theorem 2.1. The cardinality of the set Z ([s.sub.1],..., [s.sub.n]) is N ([s.sub.1],..., [s.sub.n]).

Theorem 2.2. The cardinality of the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Theorem 2.3. The set of coefficient vectors for one minimal set of linear equations that define the trivial conserved functions with energy windows of size s = ([s.sub.1],..., [s.sub.n]) is {e(s, [P.sub.Z] (A)) - e(s, [P.sub.C] ([P.sub.Z] (A))) | A [member of] [??]([s.sub.1],..., [s.sub.n])}.

Theorem 2.4. The set of coefficient vectors for one set of linear equations that defines the conserved functions with energy windows of size s = ([s.sub.1],..., [s.sub.n]) for cellular automaton rule R with neighborhood ofsize w = ( [w.sub.1] , ... , [w.sub.n]) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Theorem 2.5. The set T ([s.sub.1],..., [s.sub.n]) is a basis set for the space of all trivial additive conserved functions with energy windows of size [s.sub.1] x xxx x [s.sub.n].

Theorem 2.6. A complement of the coefficient vectors for the equations defining the trivialsfor energy windows of size [s.sub.1] x,..., x [s.sub.n] is {[V.sub.t] (M) | M [member of] Z}.

Note that by the definition of complements, this implies that when searching for conserved functions, without loss of generality we can constrain the energy functions to assign an energy of 0 to any window that is a zero-sided tensor. This corresponds to deleting certain columns in the matrix that defines the conserved functions. After that deletion, there will be solutions to those equations if and only if nontrivials exist. If such solutions do exist, then those solutions are guaranteed to be nontrivial conserved functions, and the union of those solutions with the trivials will span the space of conserved functions. This allows faster searches for nontrivials.

Figure 1 summarizes all the theorems of this paper, giving four examples of the M matrix for each concept. Figure 2 applies the ideas of this paper to the results of [1] and [3], expressing the basis functions as a linear sum of the matching H-functions of Definition 1.10.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

3 Computational results

The challenge in identifying cellular automata with a nontrivial additive energy conservation function (hereafter referred to as a "nontrivial") is the enumeration of the trivial functions and their elimination from the solution space. The actual calculation of the nontrivials can then be reduced to the calculation of the null space of the system of corresponding state space equations. Thus the theorems and definitions of the previous section may be used as the basis for computational identification of cellular automata with nontrivials of various orders. Computationally, this proceeds as follows:

1) Choose a CA and energy window size ([s.sub.1], [s.sub.2]).

2) For all possible matrices M given by Theorem 2.4, generate the corresponding state space equations.

3) To remove the trivials from the solution space, delete the columns associated with the zero-sided tensors as determined by Theorem 2.6. This has the additional benefit of significantly reducing the size of the energy vectors and, therefore, the state space matrix as a whole.

4) Determine the rank of the resulting matrix. If it is full rank, the system of equations has no solution, and therefore no nontrivial exists for the given CA and window size. If the matrix is rank-deficient, a nontrivial exists. It is completely characterized by the basis vectors that are the columns of the matrix's null space.

In [1], we gave a complete taxonomy of binary nontrivials for 1D cellular automata up for energy windows up to size 16. Using the definitions and theorems previously presented, we now extended these results to binary 2D automata, for energy windows up to size 9.

There are a total of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] k-colored 2D cellular automata (ignoring isomorphic entries). This number is so large that any investigation other than a random sampling is effectively impossible. Accordingly, drawing substantive conclusions about unrestricted 2D cellular automata seems to the authors extraordinarily difficult. To reduce the scope of the problem and make a more complete investigation possible, we consider only outer totalistic CAs: Those for which the next state of the cell is a function only of the total number of colors of a given type in the region surrounding the cell and the cell itself. For binary CAs, this means that only the total number of l's in a cell's neighborhood (including its own value) must to be calculated to determine the cell's next state. Conway's Game of Life is a cellular automaton of this type.

Restricting the search space to outer totalistic automata significantly reduces the size of the problem. For a 2D CA, the neighborhood is of size 9, and therefore the total number of occupied cells in a cell's neighborhood ranges from 0 through 8. For binary automata, one of four outcomes are possible: (S)ame, (B)irth, (D)eath, and (F)lip (Flip changes 0 to 1 and vice versa). Thus any outer totalistic CA can be represented as a character string of the form S,B,D,F. Using this notation, if we count the neighbors from 0 to 8 from left to right, Conway's Game of Life would be written as "DDSBDDDDD". We refer to this description at the CA's rule vector. Note that the use of symbols S and F permits the incorporation of the central state into the transition rule.

It is known that renumbering the colors of a CA in reverse order and changing the outcomes correspondingly produces an CA identical to the original, up to isomorphism. Using the proposed notation, this corresponds to reversing the order of the letters, swapping S with F, and swapping B with D. The rule vector of every CA can be manipulated in this way to produce a unique and distinct isomorph, so the total number of unique totalistic binary CAs is [4.sup.9]/2 = [2.sup.17]. This is considerably smaller than the non-totalistic case.

The definitions and theorems in this paper give the dimensions of the matrices to be analyzed as a function of the energy window (independent of the CA being analyzed). We show the matrix sizes for some 2D examples in Table 1.

Column three shows the ceiling of the log base 2 of the maximum number of energy vectors needed to determine the existence of a nontrivial. Column four shows the number of entries in each vector. This is given by the total number of possible energy function values ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]) minus the number of zero-sided tensors given by Definition 1.15.

Because these matrices have far more rows than columns, we expect almost all of them to be full rank, and therefore few nontrivial conservation functions should exist over the range of cellular automata. Since full rank can be determined very quickly while rank-deficiency cannot be known until all the possible state space vectors given by Theorem 2.3 have been examined for linear independence, it would be inefficient to build the full state space matrix for each CA and then calculate its rank. Instead, we sift the sands of cellular automata through a three-stage computational sieve.

The first stage uses a "quick and dirty" algorithm to discard automata with no nontrivials. This eliminates over 99% of the candidates. The second stage takes automata that have passed the first stage and performs a little more work to try and drive the set of state space matrices to full rank. This eliminates about another 90% of the candidates it analyzes. The third stage operates only on automata that have passed the first two stages, performing exact arithmetic using all the optimizations of Theorem 2.3 to determine whether or not a given CA has a nontrivial conservation function. If it does, its basis is calculated and reported. Each stage is implemented in MATLAB.

In stage I, we compute the energy vector of Definition 1.14 for one tensor at a time, attempting to add it to an existing energy vector set via Gaussian elimination to ensure that the rows in the state space matrix at any time are always linearly independent. Before such addition, however, we delete the columns corresponding to the zero-sided tensors for the indicated energy window. The total number of deleted columns is given by Definition 1.15. None of the optimizations discussed in the proof of Theorem 2.3 are performed at this stage. Instead, universe states are generated randomly, the energy vectors of their corresponding tensors are calculated, and Gaussian elimination is performed on each vector relative to those energy vectors already admitted into the state space matrix. When the number of linearly independent energy vectors is equal to the number of columns (the number of possible energy function values minus the number of zero-sided tensors), full rank has been achieved, and the CA/energy window pair under test is known not to correspond to a nontrivial conservation function.

Since states are generated randomly in this stage, as opposed to exhaustive enumeration of the appropriate tensors as given by Theorem 2.3, the number of states N to try before giving up on the possibility of reaching full rank is a user-definable parameter. Empirically, we have found that setting N at 32x the maximum rank of the matrix gives a good tradeoff between quick computation on the one hand and admitting too many false positives on the other.

During this stage, all arithmetic is performed modulo a small prime, to eliminate the possibility of roundoff error or overflow. If full rank is reached, the matrix would be full rank in exact arithmetic as well, so the answer is correct. If full rank is not reached within the indicated time window, the matrix may or may not be rank-deficient, so the CA is marked as a candidate for stage II computation.

In stage II, candidate CA/window pairs that pass through the first stage are subject to repeated random state generation with a larger value of N for multiple attempts. No other optimizations are performed at this time. If no full rank matrix is produced (i.e. no linearly independent energy vector set of the cardinality given by Definition 1.14 is found), the pair is marked for analysis by stage III.

Stage III computation employs on-the-fly Gaussian elimination for one-at-a-time energy vector generation, similar to the first two stages, but using double precision arithmetic and enumerating the state space exactly as described in the proof of Theorem 2.3. To keep the computations from overflowing, vectors are reduced modulo the GCD of all their nonzero entries during this process, which means this stage is the most computationally intensive. If Gaussian elimination on the entire set of energy vectors does not produce a linearly independent set of Definition 1.14 cardinality, then constructed state space matrix has a null space. That null space is calculated, and reported as the basis for all nontrivial conservation functions for that particular CA/window combination.

To guard against the possibility of numerical error, the largest value observed during stage III calculation is tracked and reported, to ensure that any possibility of overflow or loss of precision will be detected. For all calculations reported here, this maximum value has always been well below that which could induce error in double precision arithmetic. So we are confident our results are correct. Nonetheless, as an added safety check, we have implemented code which accepts as input a CA, an energy window, and a stage III basis set reported as characterizing a nontrivial. It tests each vector in the basis set over large numbers of randomly selected states by evaluating the energy function through brute force dot product calculation. In all cases, the resulting functions reported by stage III were conserved.

Table 2 shows the results of our computations for all outer totalistic binary 2D cellular automata up to isomorphism, for all energy windows up to order 9. It extends [1] to give a complete taxonomy of conservation functions for all automata of this type. Figures 3 and 4 are similar to Figure 2, extended to two dimensions. Figure 5 summarizes our current knowledge of 1D conservation functions.

The first three columns of Table 2 are all different ways of identifying the same automaton. The first column is the decimal integer represented by a CA's rule vector, obtained by treating the symbols S,B,D,F as the integers 0,1,2,3 respectively, and viewing the rule vector as a number in base 4 with the most significant digit on the right. The second column shows the CA rule using the notation in [8]. Column three is the CA's rule vector.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

Columns four through six describe the nontrivial conservation function found. Column four shows the dimensions of the energy window at which the first nontrivial was discovered. Column five shows the number of basis vectors in the null space of the CA's state matrix for an energy window of the indicated size. Column six contains, where appropriate, comments describing the conservation function. A blank entry in this column means that either no simple description exists or that describing the pattern would be too complex to fit within the indicated space.

Symmetry arguments will show that analogous conservation functions for any m x n window can also be found for one that is n x m. Thus the only energy windows examined were those that were at least as wide as they were tall.

4 Analysis

Some patterns are clearly visible in Table 2, Figure 3, Figure 4 and Figure 5. For all CA's for which non-trivial conservation functions exist, there is a great deal of homogeneity in the middle range of neighbor counts. For example, any given CA in the table has the same transition rules for neighbor counts 3-6, and most have identical transition rules for neighbor counts 2-7. We conjecture this is combinatorically driven. That is, for the middle range of neighbor counts, there are so many different ways to distribute a fixed number of neighbors among eight cells that a low-order conservation function cannot incorporate them all. By contrast, there is only one way to arrange zero or eight neighbors around a cell, eight ways to arrange one or seven, and so forth. Near the minimum and maximum of the neighbor count range, the number of possible configurations is sufficiently small that a low-order conservation function is more likely to emerge.

We also note that all CA's with rule vectors of the form xFFFFFFFx, xSSSSSSSB, and xDSSSSSSB have nontrivial conservation functions. All CA's of the form xSSSSSSSx have a nontrivial as well, unless exactly one of the x's is 'S'.

Finally, our results show that all known nontrivials correspond to energy windows for which the width and the height differ by no more than one. Whether this holds true for all nontrivials remains an open question.

5 The Game of Life

Because of the special significance of Conway's Game of Life (CA #174666, rule B3/S23, rule vector DDSBDDDDD), we have examined it for nontrivial energy conservation functions up to order 13. None have been found.

6 Conclusions and Future Work

Table 2 and Figures 3 through 5 represent a complete taxonomy of all known nontrivial conservation functions for 1- and 2-dimensional binary cellular automata up to isomorphism. We have discussed some of the patterns we have observed.

[1] introduced the notion of core nontrivials, recognizing that cellular automata could exhibit different nontrivials of higher orders that are not simple extensions of lower ones. We have yet to apply this idea to the automata shown here. Thus the functions we report are only the first core nontrivials found. The existence of multiple cores for 2D binary cellular automata remains an open question. Detecting such cores requires only well-understood modifications to our existing code, and is on our list of future enhancements.

Number-conserving 1D cellular automata [2] are automata with transition rules that conserve the sum of the number of states in a neighborhood. A number-conserving function is one kind of energy conservation function defined in Definition 1.8, where the function is simply the sum of all terms in the window. Our work therefore includes number-conservation as a special case. The theory described here applies to all cellular automata with finite states and arbitrary dimensionality. The results for 2D automata are all new.

Continuing improvements in computing power and further refinements of our codes should enable us to identify nontrivials at increasingly higher orders. The existence of nontrivialss for m x n energy windows with [absolute value of m - n] > 1 remains an open question. Higher dimensional CAs, non-totalistic CAs, and k-colored CAs could also be explored.

As yet, an elegant, unifying description of cellular automata relating their decision rules and a given energy window to a nontrivial conservation function remains elusive. While the general problem is undecidable, we have mapped out the space for lower orders and binary outer totalistic CAs well enough to suggest some ideas for a more elegant classification scheme than the present ad hoc one we are currently forced to adopt. Such a scheme may in fact exist, or it may remain forever elusive, an fundamentally complex property inherent in the nature of computational automata. We hope further work may yet resolve this question.

7 Errata and Acknowledgments

Readers unfamiliar with automata conservation functions may wish to review [1]. In the course of preparing this paper, we noticed errors in the first three tables of our previous results. For the sake of completeness, we present the necessary corrections to [1] here:

TABLE 1: Replace 98 with 94, replace 40 with 46

TABLE 2: Replace 136 with 200

TABLE 3: Replace 136 with 200, replace 248 with 232

The authors are grateful for the support of the Air Force Academy Center for Cyberspace Research, and to the reviewers for their helpful comments.

References

[1] L. Baird and B. Fagin, Conservation functions for 1-d automata: Efficient algorithms, new results, and a partial taxonomy, Journal of Cellular Automata 3 (2008), no. 4, 271-288.

[2] Nino Boccara and Henryk Fuks, Number-conserving cellular automaton rules, Fundam. Inform. 52 (2002), no. 1-3, 1-13.

[3] B. Fagin and L. Baird, New higher-order conservation functions for 1-d cellular automata, Proceedings of the IEEE Symposium on Artificial Life, April 1-5 2007.

[4] H. Fuks, Remarks on the critical behavior of second order additive invariants in elementary cellular automata, Fundamenta Informaticae 78 (2007), 329-341.

[5] T. Hattori and S Takesue, Additive conserved quantities in discrete-time lattice dynamical systems, Physica D 49 (1991), 295-322.

[6] L. Kotze and W.H. Steeb, Finite dimensional integrable nonlinear dynamical systems, pp. 333-346, World Scientific Publishing, New Jersey, 1998.

[7] M. Pivato, Conservation laws in cellular automata, Nonlinearity 15 (2002), 1781-1793.

[8] Wikipedia, Life-like cellular automaton, http://en.wikipedia.org/wiki/Life-like_cellular_automaton, March 2010.

[9] S. Wolfram, A new kind of science, Wolfram Media Inc., 2002.

Leemon Baird and Barry Fagin

Academy Center for Cyberspace Research, Department of Computer Science, US Air Force Academy, Colorado Springs, Colorado USA 80840
Tab. 1: State matrix sizes for various energy windows

Energy window   Energy window
height          width ([s.sub.2])   [[log.sub.2] rows]   [[log.sub.2]
([s.sub.1])                                              cols]

1               2                   16                   1
1               3                   19                   2
1               4                   23                   3
                2                   20                   4
1               5                   26                   4
1               6                   29                   5
                3                   25                   6
1               7                   32                   6
1               8                   35                   7
2               4                   29                   8
1               9                   39                   8
3               3                   30                   9

Tab. 2: Conservation functions of order [less than or equal to]9 for 2D
CA's

CA#      Rule                   rule vec (num neighbors)        min
                                                                NCF
                           0   1   2   3   4   5   6   7   8
0        S0123456789       S   S   S   S   S   S   S   S   S   lxl
2        S12345678         D   S   S   S   S   S   S   S   S   1x2
8        S02345678         S   D   S   S   S   S   S   S   S   2x2
10       S2345678          D   D   S   S   S   S   S   S   S   2x2
21       B012/S012345678   B   B   B   S   S   S   S   S   S   3x3
32       S01345678         S   S   D   S   S   S   S   S   S   2x2
34       S1345678          D   S   D   S   S   S   S   S   S   2x2
40       S0345678          S   D   D   S   S   S   S   S   S   2x2
42       S345678           D   D   D   S   S   S   S   S   S   2x2
16386    B7/S12345678      D   S   S   S   S   S   S   B   S   2x2
16387    B07/S12345678         S   S   S   S   S   S   B   S   3x3
21845    B01234567/S8      B   B   B   B   B   B   B   B   S   3x3
65532    B1234567/S8       S   F   F   F   F   F   F   F   S   2x3
65533    B01234567/S08     B   F   F   F   F   F   F   F   S   2x3
65534    B1234567/S8       D   F   F   F   F   F   F   F   S   2x3
65535    B01234567/S8      F   F   F   F   F   F   F   F   S   2x3
65537    B08/S012345678    B   S   S   S   S   S   S   S   B   2x3
65538    B8/S12345678      D   S   S   S   S   S   S   S   B   2x2
65539    B08/S12345678     F   S   S   S   S   S   S   S   B   2x3
65541    B018/S012345678   B   B   S   S   S   S   S   S   B   3x3
65545    B08/S234567       B   D   S   S   S   S   S   S   B   2x3

65546    B8/S234567        D   D   S   S   S   S   S   S   B   2x2
65547    B08/S2345678          D   S   S   S   S   S   S   B   2x3
65549    B018/S02345678    B   F   S   S   S   S   S   S   B   3x3
81921    B078/S012345678   B   S   S   S   S   S   S   B   B   2x3
81923    B078/S12345678        S   S   S   S   S   S   B   B   2x3
131069   B012345678/S08    B   F   F   F   F   F   F   F   B   2x3
131070   B12345678/S8      D   F   F   F   F   F   F   F   B   2x3
131071   B012345678/S8     F   F   F               F   F   B   2x3
131073   B0/S01234567      B   S   S   S   S   S   S   S   D   2x3
131075   B0/S1234567       F   S   S   S   S   S   S   S   D   2x3
131077   B01/S01234567     B   B   S   S   S   S   S   S   D   3x3
131081   B0/S0234567       B   D   S   S   S   S   S   S   D   3x3
131083   B0/S234567        F   D   S   S   S   S   S   S   D   3x3
131085   B01/S234567       B   F   S   S   S   S   S   S   D   3x3
147459   B07/S1234567      F   S   S   S   S   S   S   B   D   3x3
163483   B0/S123456        L   S   S   S   S   S   S   D   D   3x3
180227   B07/S123456       F   S   S   S   S   S   S       D   3x3
196605   B01234567/S0      B   F   F   F   F   F   F   F   D   2x2
196607   B01234567         F   F   F   F   F   F   F   F   D   2x2
196611   B08/S1234567      F   S   S   S   S   S   S   S   F   2x3
196619   B08/S234567       F   D   S   S   S   S   S   S   F   3x3
262143   B012345678        F   F   F   F   F   F   F   F   F   1x2

CA#      basis   comments
         size

0        n/a     identity, conserves all
2        1       conserves [11] pairs
8        5       conserves 2x2 patterns with > 3 l's
10       5       identical to 8
21       1
32       1       conserves 2x2 pattern with all l's
34       1       identical to 32
40       1       identical to 32
42       1       identical to 32
16386    4
16387    11
21845    1       conserves ring of l's around a 0
65532    1
65533    1       identical to 65532
65534    1       identical to 65532
65535    1       identical to 65532
65537    7
65538    8
65539    7       identical to 65537
65541    1       conserves [001 011 010]
65545    1       conserves the difference
                 between [101 ill] and [ill 101]
65546    4       conserves 2x2 patterns with > 3 l's
65547    1       identical to 65545
65549    1       identical to 65541
81921    1
81923    1       identical to 81921
131069   1       identical to 65532
131070   1       identical to 65532
131071   1       identical to 65532
131073   2
131075   2       identical to 131073
131077   1       identical to 65541
131081   9
131083   9       identical to 131081
131085   1       identical to 65541
147459   9
163483   1       conserves [011 100 101]
180227   1       identical to 163843
196605   4
196607   4       Identical to 196605
196611   2       Identical to 131073
196619   9       Identical to 131081
262143   1       Conserves [10] pairs
COPYRIGHT 2010 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2010 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Baird, Leemon; Fagin, Barry
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2010
Words:6540
Previous Article:An immanant formulation of the dual canonical basis of the quantum polynomial ring.
Next Article:60/102 Null Boundary Cellular Automata based expander graphs.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters