Complex Systems

Local Nested Structure in Rule 30 Download PDF

Eric S. Rowland
Department of Mathematics,
Rutgers, The State University of New Jersey,
Piscataway, NJ 08854, USA


At row 2n in the cellular automaton rule 30, a region of the initial condition reappears on the right side, which causes the automaton to "begin again" locally. As a result, local nested structure is produced. This phenomenon is ultimately due to the property that rule 30 is reversible in time under the condition that the right half of each row is white. The main result of the paper establishes the presence of local nested structure in k-color rules with this bijectivity property, and we explore a class of integer sequences characterizing the nested structure. We also prove an observation of Wolfram regarding the period length doubling of diagonals on the left side of rule 30.