Book contents
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Probabilizing Fibonacci Numbers
- 2 On the Number of ON Cells in Cellular Automata
- 3 Search for Ultraflat Polynomials with Plus and Minus One Coefficients
- 4 Generalized Gončarov Polynomials
- 5 The Digraph Drop Polynomial
- 6 Unramified Graph Covers of Finite Degree
- 7 The First Function and Its Iterates
- 8 Erdős, Klarner, and the 3x + 1 Problem
- 9 A Short Proof for an Extension of the Erdős–Ko–Rado Theorem
- 10 The Haight–Ruzsa Method for Sets with More Differences than Multiple Sums
- 11 Dimension and Cut Vertices: An Application of Ramsey Theory
- 12 Recent Results on Partition Regularity of Infinite Matrices
- 13 Some Remarks on π
- 14 Ramsey Classes with Closure Operations (Selected Combinatorial Applications)
- 15 Borsuk and Ramsey Type Questions in Euclidean Space
- 16 Pick's Theorem and Sums of Lattice Points
- 17 Apollonian Ring Packings
- 18 Juggling and Card Shuffling Meet Mathematical Fonts
- 19 Randomly Juggling Backwards
- 20 Explicit Error Bounds for Lattice Edgeworth Expansions
- References
2 - On the Number of ON Cells in Cellular Automata
Published online by Cambridge University Press: 25 May 2018
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Probabilizing Fibonacci Numbers
- 2 On the Number of ON Cells in Cellular Automata
- 3 Search for Ultraflat Polynomials with Plus and Minus One Coefficients
- 4 Generalized Gončarov Polynomials
- 5 The Digraph Drop Polynomial
- 6 Unramified Graph Covers of Finite Degree
- 7 The First Function and Its Iterates
- 8 Erdős, Klarner, and the 3x + 1 Problem
- 9 A Short Proof for an Extension of the Erdős–Ko–Rado Theorem
- 10 The Haight–Ruzsa Method for Sets with More Differences than Multiple Sums
- 11 Dimension and Cut Vertices: An Application of Ramsey Theory
- 12 Recent Results on Partition Regularity of Infinite Matrices
- 13 Some Remarks on π
- 14 Ramsey Classes with Closure Operations (Selected Combinatorial Applications)
- 15 Borsuk and Ramsey Type Questions in Euclidean Space
- 16 Pick's Theorem and Sums of Lattice Points
- 17 Apollonian Ring Packings
- 18 Juggling and Card Shuffling Meet Mathematical Fonts
- 19 Randomly Juggling Backwards
- 20 Explicit Error Bounds for Lattice Edgeworth Expansions
- References
Summary
Abstract
If a cellular automaton (CA) is started with a single ON cell, how many cells will be ON after n generations? For certain “odd-rule” CAs, including Rule 150, Rule 614, and Fredkin's Replicator, the answer can be found by using the combination of a new transformation of sequences, the run length transform, and some delicate scissor cuts. Several other CAs are also discussed, although the analysis becomes more difficult as the patterns become more intricate.
Introduction
When confronted with a number sequence, the first thing is to try to conjecture a rule or formula, and then (the hard part) prove that the formula is correct. This chapter had its origin in the study of one such sequence, 1, 8, 8, 24, 8, 64, 24, 112, 8, 64, 64, 192, … (A1602391), although several similar sequences will also be discussed.
These sequences arise from studying how activity spreads in cellular automata (for background see [2, 5, 8, 11, 14, 17, 20, 21, 23, 24, 26]). If we start with a single ON cell, how many cells will be ON after n generations? The preceding sequence arises from the CA known as Fredkin's Replicator [13]. In 2014, Hrothgar sent the author a manuscript [10] studying this CA, and conjectured that the sequence satisfied a certain recurrence. One of the goals of the present chapter is to prove that this conjecture is correct; see (2.31).
In §2.2 we discuss a general class (the “odd-rule” CAs) to which Fredkin's Replicator belongs, and in §2.3 we introduce an operation on number sequences (the “run length transform”) that helps in understanding the resulting sequences. Fredkin's Replicator, which is based on the Moore neighborhood, is the subject of §2.4, and §2.5 analyzes another odd-rule CA, based on the von Neumann neighborhood with a center cell. Although these two CAs are similar, different techniques are required for establishing the recurrences. Both proofs involve making scissor cuts to dissect the configuration of ON cells into recognizable pieces.
- Type
- Chapter
- Information
- Connections in Discrete MathematicsA Celebration of the Work of Ron Graham, pp. 13 - 38Publisher: Cambridge University PressPrint publication year: 2018