Representations of Rule 90 and Related Rules for Periodic, Null, and Half-Infinite Boundary Conditions

摘要

An analysis of elementary cellular automata rule 90 subject to periodic, null, and half-infinite boundary conditions is given. In the case of periodic and null boundaries, representation of this rule in matrix form allows computation of transient lengths and cycle periods through computation of the characteristic polynomials and minimal annihilating polynomials of these matrices. Formula are given relating the action of rule 90 with periodic boundary conditions to its action with null boundary conditions, and a method for approximating the action of rule 90 on half-infinite sequences by its action on periodic sequences is given. In the case of half-infinite boundary conditions, two families of associated mappings of the state space of half-infinite binary sequences are defined and some properties of these mappings are determined.