It is well-known that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo 2 generates a Sierpinski triangle. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose typical features include irreversibility, an alphabet with a ring structure, a global evolution that is a ring homomorphism, and a property known as (weakly) p-Fermat. The class of automata that we study in this article has none of these properties. Their cell structure is weaker, as it does not come with a multiplication, and they are far from being p-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we explain why and how.
[ @cite_7 ] Macfarlane uses Willson's approach and generalizes parts of it to some examples of matrix-valued CAs, including @math . However, the transition matrix is obtained heuristically --- by scrutiny of figure 9'' --- from the spacetime diagram, instead of being algorithmically derived from the transition rule (as in the present work). The conclusion (section 6) suggests that the analysis of @math is easily generalizable to matrices of various sizes over various rings, so in a sense the present article is but an elaboration of the concluding remark of @cite_7 , although we have to say we do not find this generalization to be that obvious.
@cite_7
2029310694
Linear or one-dimensional reversible second-order cellular automata, exemplified by three cases named as RCA1–3, are introduced. Displays of their evolution in discrete time steps, , from their simplest initial states and on the basis of updating rules in modulo 2 arithmetic, are presented. In these, shaded and unshaded squares denote cells whose cell variables are equal to one and zero respectively. This paper is devoted to finding general formulas for, and explicit numerical evaluations of, the weights N(t) of the states or configurations of RCA1–3, i.e. the total number of shaded cells in tth line of their displays. This is achieved by means of the replacement of RCA1–3 by the equivalent linear first-order matrix automata MCA1–3, for which the cell variables are matrices, instead of just numbers () as for RCA1–3. MCA1–3 are tractable because it has been possible to generalize to them the heavy duty methods already well-developed for ordinary first-order cellular automata like those of Wolfram's Rules 90 and 150. While the automata MCA1–3 are thought to be of genuine interest in their own right, with untapped further mathematical potential, their treatment has been applied here to expediting derivation of a large body of general and explicit results for N(t) for RCA1–3. Amongst explicit results obtained are formulas also for each of RCA1–3 for the total weight of the configurations of the first times, .