arXiv preprint ·

Rule-table structure of life-like cellular automata: activity, asymmetry, sensitivity, and the propagation storage factorisation

Yair Cohen

Published
Source
arXiv preprint, posted before peer review
Original
Read it at arXiv
Topics
Populations & EvolutionMachine Learning

Abstract

What structure on the rule space of a cellular-automaton family exposes which rules can support which behaviours? For the 262,144 life-like rules -- the two-dimensional outer-totalistic family containing Conway's Game of Life -- the standard coordinate, Langton's activity parameter, is long known to be too coarse. I organise the family by three symmetry-derived rule-table coordinates: an unweighted activity, a birth-survival asymmetry (odd under the swap of birth and survival), and the Vichniac-Binder Boolean-derivative sensitivity in closed form, whose centre-bit component vanishes exactly on the centre-blind (B=S) submanifold. The cardinality coordinates lambda, delta are necessary but never sufficient to certify behaviour; the centre-bit sensitivity labels the B=S submanifold on which the paper's one exact exclusion holds. Combined with an exhaustive enumeration of every rule's compact gliders, still lifes and oscillators (three-by-three seed, period at most sixteen), they expose a hierarchical factorisation: the birth condition is a narrow gate deciding whether anything can propagate, the survival condition tunes storage, and every compact-glider-supporting rule is birth-light and survival-rich. One exclusion is exact: no B=S rule supports a compact glider at that footprint, proven by exhaustive enumeration and closing only for compact-footprint patterns -- 36 B=S rules ship at four-by-four seed and 40 at five-by-five. Two dynamical results frame the whole: glider-capable rules that random sampling never expresses show that capability is certifiable from the table while its expression is only estimable from dynamics; and every uncatalogued rule producing a richly Life-like ecology turns out to be a Conway or HighLife variant on the neighbour counts its trajectories actually visit.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Populations & Evolution

Get the few papers worth your time in Populations & Evolution every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics