actinophrys wrote: January 2nd, 2026, 1:34 pm
Unfortunately both of those use a method for dividing periods that does not always work. Basically if you have an oscillator of period n, then for m|n you take the sum of its states at generations 0, m, 2m, ..., (n-1)m/n. But this only guarantees a pattern that
repeats itself every m turns, which is weaker than it having
period m.
For instance for m = 9 you could end up with a p9, p3, or p1, and in fact
trying that with the rule 150 emulator actually only gives a p1. For the Margolus-emulating rules creeperman7002 gives two candidates, so
e.g. starting with 64 Margolus blocks fails to give a p14 but then 62 succeeds. But an actual proof would still need to show one of the two must always work. Since
Johnston (2010) only concludes that periods of the form 2^k*(2^m-1) exist and says nothing about all even periods it doesn't seem likely to be trivial.
This is a very good point, and reading this made me realize that this is also a flaw in
my recent "proof" of photon omniperiodicty in B25678/S35678 based on Rule 150 emulation. Fortunately, I have found a remedy in this case (I don't know about the 2x2 case
Edit: I think this actually solves the 2x2 case as well; see the edits at the bottom of this post).
Proof of omniperiodicity in Rule 150 on arbitrary-finite-length lines with cylindrical, always-on, or always-off boundary conditions:
In this proof, the evolution of a pattern in Rule 150 is depicted as a stack of rows, where the top row is pattern in generation 0, the next row is the pattern in generation 1, etc. By cylindrical boundary conditions, we mean that the left edge of the finite line connects to the right edge. As a helpful reference, below is every set of 4 cells in a row (top row) and the result of evolving the two center cells of each set using Rule 150 (red = off in gen. 0; yellow = on in gen. 0; blue = off in gen. 1; white = on in gen. 1):
Code: Select all
x = 244, y = 2, rule = W150History
4D6.E3D6.3DE6.E2DE36.DE2D6.2E2D6.DEDE6.2EDE36.2DED6.EDED6.2D2E6.ED2E
36.D2ED6.3ED6.D3E6.4E$.2B8.CB8.BC8.2C38.2C8.BC8.CB8.2B38.2C8.BC8.CB8.
2B38.2B8.CB8.BC8.2C!
The idea of the proof is that we can arbitrarily pick the complete cell histories of two adjacent cells (i.e, we can pick the states of every generation of a pair of adjacent cells), and this will completely determine the initial (infinite) pattern. The argument is by induction. In the base case, we can obviously just pick the states of two adjacent cells in gen. 0. Now consider picking the states of one of the two cells in generation 1. That is, suppose we already know the states of the grey cells (in gen. 0) below, and we want to choose the state of the green cell (in gen. 1):
Code: Select all
x = 3, y = 2, rule = W150History
D2F$.A!
Carefully checking the above collection of the evolution of 4-cell sets, we see that we can choose the green cell (in gen. 1) to be whichever state we want, but this will uniquely determine the state of the red cell (in gen. 0). Likewise, suppose we have made such a choice, so that the grey cells are forced, and we wish to choose the state of the adjacent cell in gen. 1 (green in the diagram below):
Code: Select all
x = 4, y = 2, rule = W150History
3FD$.FA!
Notice again (by checking the cases) that we can choose either state for the green cell (in gen. 1) without conflicting with the previously determined cells, and that this forces the state of the red cell (in gen. 0). We can continue this process inductively with larger triangles of previously determined cells:
Code: Select all
x = 36, y = 8, rule = W150History
D14F5.15FD$.D12F7.13FD$2.D10F9.11FD$3.D8F11.9FD$4.D6F13.7FD$5.D4F15.
5FD$6.D2F17.3FD$7.A19.FA!
We can again make an arbitrary choice of the state of the green cells without conflict with the previously set cells for the same reason we could in the gen. 1 case. Picking the state of the green cell in generation n then forces the red cell in generation n-1, which forces the red cell in gen. n-2, etc. Therefore, if we choose the state of each of these two cells in all (infinitely many) generations, we see that the state of any cell in generation 0 is forced. Since nothing restricted our choice of the green cells, we could pick any cell histories we want for these two cells.
I'm sure the above fact has been long known, and is probably written up in some much more general form in a paper somewhere. If anyone finds a reference, please post it here.
Edit: I have found just such a reference. This fact was apparenty first published by Mark A. Shereshevsky and Valentin S. Afraimovich in 1992 and independently by Masakazu Nasu in 1995, according to
Jeremias Epperlein's dissertation. Epperlein even explicitly mentions the cases of Rule 150 and Rule 90 and includes other interesting results in classifying elementary cellular automata that might be helpful in proving omniperiodicity results.
The above fact for Rule 150 is a special case of Theorem 6.3 in the linked dissertation. In this case the alphabet A is {0, 1} (the set of possible cell states), the left and right radii are both 1 (because Rule 150 and Rule 90 have a symmetric neighborhood of radius 1), and f_{loc} is just the application of the rule for just one cell. The "left and right permutivity" just mean that if we know the state of k adjacent cells in generations n and n+1, then this uniquely determines the state of the cells immediately to the left and right of the k cells in generation n.
The "conjugacy" is just a type of isomorphism between the CA rule on the infinite line and the left-shift map on a sequence of pairs of cell states. Specifically, the isomorphism maps a pattern in Rule 150 to the sequence of cell states of the cells at coordinates (-1) and (0) as they evolve under Rule 150. That is, the element a_n in the sequence is the nth generation of the cell pair at coordinates (-1) and (0). The left shift on this sequence just means removing the element a_0 and shifting the remaining elements indices down by 1. Since this is an isomorphism, and hence a bijection, it means we can make an arbitrary choice of the history of a pair of cells (this is the sequence a_n) and it corresponds to exactly one pattern on an infinite line.
We can choose cell histories of the desired period, and this gives oscillators of that period on some finite-length line with cylindrical, always-on, or always-off boundary conditions:
First, consider patterns on the infinite line, and let n be the desired period for which we want to construct an oscillator. Since we can arbitrarily choose the cell histories of two adjacent cells, we can simply choose them to have a period-n cell history (here we consider the period of the
pair of cells, not of each cell individually). Notice that the full cell histories of the pair of cells starting in generation n completely determines the pattern in generation n, but the cell history starting in generation n is identical to the cell history starting in generation 0, so generation n is equal to generation 0, and thus the entire (infinite) pattern has period n. We can immediately see that any pair of adjacent cells will also have period n, because if it had a period k properly dividing n, then the cell histories of that pair would force the overall pattern to have period k.
Suppose we have chosen a period-n history for a pair of adjacent cells. There are, of course, only a finite number of possible period-n histories for a pair of cells, and all (infinitely many) pairs of cells have period n, so by the pigeonhole principle there are two non-intersecting pairs of cells with the exact same life history. Because any single pair of full life histories determines the entire infinite pattern, this means that the pattern is periodic in space, and thus lives on a cylinder. This proves omniperiodicity with cylindrical boundary conditions.
Now we can simply choose one cell to always be on and the other cell to have period n. Note that having one cell be period-1 does not force the rest to be period-1, as only the history of a
pair of adjacent cells can determine the full pattern. We then cut our cylinder immediately to the left of the always-on cell. Due to the cylindrical boundary conditions, the right edge of the finite line is adjacent to the leftmost always-on cell, so we can consider all of the cells in the cylinder that are not the leftmost cell as being bounded by always-on cells. This proves omniperiodicity with always-on boundary conditions.
To prove omniperiodicity with always-off boundary conditions, note that we could have performed the same procedure above, but instead setting the period-1 cell to always be off, rather than always on. This concludes the proof.
Fixing the omniperiodicity proof in B34kz5e7c8/S23-a4ityz5k:
The
claimed omniperiodicity proof was based on Rule 150 emulation on finite lines with an always-on cell at one end and an always-off cell at the other end:
Code: Select all
x = 15, y = 15, rule = B34kz5e7c8/S23-a4ityz5k
8bo$8b3o$6b2o3bo$7bob2obo$6bobo2bobo$5bobo3bobo$4bobo3bo2b2o$3bobo3bob
2o$2bobo3bobobo$bobo3bobo$obo3bobo$bo3bobo$4bobo$3bobo$4bo!
Unfortunately, the above proof does not work for such boundary conditions, but fortunately the stator can easily be made symmetric, which then emulates finite lines with always-on boundary conditions, and the the desired result follows from the above proof:
Code: Select all
x = 26, y = 26, rule = B34kz5e7c8/S23-a4ityz5k
19bo$19b3o$17b2o3bo$18bob2obo$17bob2obobo$16bobo2b2obo$15bobo3bo2b2o$
14bobo3bob2o$13bobo3bobobo$12bobo3bobo$11bobo3bobo$10bobo3bobo$9bobo3b
obo$8bobo3bobo$7bobo3bobo$6bobo3bobo$5bobo3bobo$2bobobo3bobo$2b2obo3bo
bo$2o2bo3bobo$bobo3bobo$bobo2bobo$2bob2obo$3bo3b2o$4b3o$6bo!
According to
the 2x2 wiki page, these block oscillators emulate
Rule 90 in some way, although I didn't make the effort to fully understand it. The above argument for Rule 150 also works for Rule 90, as Rule 90 also has the property that an arbitrary choice of full cell histories for two adjacent cells uniquely determines the (infinite) pattern in generation 0. Here is the set of 4-cell lines showing the evolution of the center two cells using Rule 90 that can be used to verify this fact:
Code: Select all
x = 244, y = 2, rule = W90History
4D6.E3D6.3DE6.E2DE36.DE2D6.2E2D6.DEDE6.2EDE36.2DED6.EDED6.2D2E6.ED2E36.
D2ED6.3ED6.D3E6.4E$.2B8.CB8.BC8.2C38.BC8.2C8.2B8.CB38.CB8.2B8.2C8.BC38.
2C8.BC8.CB8.2B!
If the emulation of Rule 90 by these block oscillators can be viewed as having cylindrical, always-on, or always-off boundaries, then this should recover a proof of all even periods in 2x2.
Edit 2: after some discussion with DroneBetter on Discord, I think this can indeed prove the existence of all even periods in 2x2. The Rule 90 emulation acts on a set of rectangles that are XOR-pasted together. If the rectangles have side lengths that are multiples of 4, then every two generations these rectangles emulate Rule 90 on an arbitrary-finite-length line with always-off boundary conditions.
Edit 3: According to
Epperlein, the elementary CA that are both left- and right-permutive are Rules 90, 105, 150, and 165 (see note at the bottom pg. 120). Thus by Theorem 6.3, the above proof should work for each of these CA. Note that Rule 165 is simply the black-white reversal of Rule 90.