2015/03/13 by Shalosh B. Ekhad, N. J. A. Sloane, Ekhad, Shalosh B. +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #37B15 #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #Primary 11B85 #math.CO #msc:11B85 #msc:37B15
paper · pdf · doi:10.48550/arxiv.1503.04249
15 pages, 3 tables, 6 figures. Mar 20 2015: corrected a typo in Fig 1
openalex publication_date 2015/03/13 · arxiv created 2015/03/21 · arxiv updated 2015/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An "odd-rule" cellular automaton (CA) is defined by specifying a neighborhood for each cell, with the rule that a cell turns ON if it is in the neighborhood of an odd number of ON cells at the previous generation, and otherwise turns OFF. We classify all the odd-rule CAs defined by neighborhoods which are subsets of a 3 X 3 grid of square cells. There are 86 different CAs modulo trivial symmetries. When we consider only the different sequences giving the number of ON cells after n generations, the number drops to 48, two of which are the Moore and von Neumann CAs. This classification is carried out by using the "meta-algorithm" described in an earlier paper to derive the generating functions for the 86 sequences, and then removing duplicates. The fastest-growing of these CAs is neither the Fredkin nor von Neumann neighborhood, but instead is one defined by "Odd-rule" 365, which turns ON almost 75% of all possible cells.