Computational Analysis of One-Dimensional Cellular Automata

The following sections are included:

• Preface

• Table of Contents

The following sections are included:

• Acknowledgements

• Biblography

• Graphs of Space–Time Output for Sample CA Rules

Cellular automata can be specified in a variety of ways: as local neighborhood maps, as global maps of a configuration space, as Boolean equations implementing truth conditions, as arithmetic recurrences, as finite replacement schemes, as maps of the interval, etc. This chapter provides an introduction to some of the standard forms in which cellular automata are presented. It also introduces the idea of representing the global map defined by a cellular automata in terms of abstract components defined with respect to a canonical basis.

This chapter introduces a division algorithm, which for given rules Q and X, allows determination of rules A and R such that Q = AX+R, with R being as small as possible. Some results in the arithmetic of residues are also derived.

Two approaches to the study of fixed points and cycles (i.e., attractors) are given. The first involves separation of CA rules into linear and non-linear parts, allowing computation of conditions for a state to be a fixed point, or to lie on a shift cycle. The second approach extends work initiated by Jen on the ennumeration of fixed points and cycles, by providing a means of counting the number of fixed points and cycles a rule will have in terms of its components.

One of the advantages of the use of abstract components is that it is possible to state general questions which can be answered by computing the solution sets of Diophantine equations in which the variables are rule components. This chapter begins with derivation of a set of such equations which, for a given k-site rule X, has solution set corresponding to all ksite rules which commute with X. The idea of commuting diagrams is introduced and used to analyze conditions under which a CA rule might be thought of as reproducing the output of a measuring instrument with output also represented by a CA rule. Finally, the division algorithm of Chapter 2 is combined with the commutation results to distinguish several interesting subgroups of the CA rule space.

In this chapter the conditions which a CA rule must satisfy in order to be additive are formulated in terms of a map from the Cartesian product of the configuration space with itself to the configuration space. This map is represented for k-site rules by a 2^k×2^k matrix. CA rules can be partitioned into equivalence classes on the basis of their additivity properties, as characterized in this matrix.

An approach to the analysis of additive rules in terms of complex polynomials is also introduced, and used to derive a condition for the injective of additive rules.

Major work on additive rules has been carried out to determine the structure of their state transition diagrams. This structure is specified in terms of such quantities as the in degree of verticies, maximum tree heights, cycle periods, and numbers of fixed points and cycles. After reviewing some of this work, some results on reachability are derived using the complex polynomial formalism developed in Chapter 5. Following this, the formalism is used to derive conditions for a configuration to lie on a cycle. Finally, two theorems are proved which show that the set of fixed points of an additive rule, and the set of all configurations on cycles, are sub-groups of the group {E_n,+}.

If ß∈ E⁺ and X is a CA rule, the predecessor problem is to find those configurations μ such that X(μ) = ß. For additive rules it is possible to find a closed form solution for the predecessors of any given configuration. This solution involves a partitioning of configurations by shuffling out sub-configurations so as to cast the predecessor equation into the form of a set of coupled equations which can be solved. The solution of these equations often involves an operator B which plays a role of integration with respect to sequence index. Following several examples of solutions, the properties of this operator are derived.

This chapter presents an analysis of the geometrical and arithmatical properties of the binary difference rule D. The first part of the chapter contains derivations of some of the basic characteristics of this rule, and then gives an analysis of the graph of D:[0,1]→[0,1]. This is followed by some number theoretic relations contained in the graph, and a theorem which demonstrates that the set of all predecessors of all orders of any point in [0,1] is uniformly distributed in [0,1].

In Chapter 7, attention was focused on computation of predecessors for configurations evolved under additive rules. The additivity condition allowed closed form solutions to be found for the predecessor equation X(μ) = ß. In the case of nonadditive rules the situation is more difficult, and no general method for computation of predecessors is known. For this reason, the goal of this chapter is more modest. A method is presented for finding the pre-image of any finite sequence ß₁…ß_n for a given rule X. That is, given such a sequence this method yields another sequence μ₁…μ_n such that if X is a k-site rule then there is a sequence s₁…s_k-1 such that X(μ_l…μ_ns₁…s_k-1) = ß₁…ß_n. In addition, it provides a method for counting how many pre-images any given sequence has. Throughout this chapter the configuration space is taken as E⁺.

The Garden-of-Eden, GE(X), for a rule X is the set of all configurations without predecessors under X. This set is most easily studied via its countable set of generators, GE*(X). A rule is surjective if and only if GE(X) = ø. If rules X and Y are related by any of the symmetry transformations T1, T2, and T3 then GE*(X) ≅ GE*(Y). The formalism introduced in Chapter 9 allows computation of GE*. In some cases the elements of GE* can be simply characterized. A first order classification of rules into four categories can be made on the basis of the set GE*, and these categories can be compared to those defined in other phenomenological classifications.

In this chapter the possibility of finding CA rules and initial conditions which generate specified time series is considered. The strongest general result is that no k-site rule can generate arbritrary time series with entries of k or more digits, while a k-site rule can generate arbritrary time series with k–1 digit entries if and only if it is linear in the final variable. A matrix technique is derived which allows determination of whether or not a given rule could have generated a specified time series, and if so what are the possible initial conditions. This allows estimation of probabilities for specified series, but these estimates are unbiased only for rules with empty Gardens–of–Eden.

A CA rule is surjective if every configuration has a predecessor. There are a number of important properties of CAs which are equivalent to surjectivity, a number of which are listed in a “kitchen sink” theorem in section 1. There are also graph theoretic techniques for the study of surjectivity, centered on the de Bruijn diagram which is defined in section 2. Another diagram, derived from the de Bruijn diagram, is the subset diagram. Both diagrams provide surjectivity criteria. Analysis of the adjacency matrix for the de Bruijn diagram allows definition of a semi-group associated to each CA rule, and several theorems on the structure of this semi-group are proved. Finally, a replacement diagram is associated to each CA rule.

The following sections are included:

• Appendix 1

• Appendix 2

• Appendix 3

• Appendix 4

• Appendix 5

• Appendix 6

• References