Omniperiodicity based on XOR replicators

[GUYTU6J]

Ideas like this (for Margolus-emulating rules) and this (for Wolfram's Rule 150-emulating rules) could easily generalize to a large varieties of rules. Still there are many questions:

Is there a more explicit formulation of construction method?
Is a helpful script available?
When does the method cover only even periods and not odd ones, and when does it cover all?
What rules are under this scheme?
...

Collect relevant information here!

[pzq_alex]

Ideas like this (for Margolus-emulating rules) and this (for Wolfram's Rule 150-emulating rules) could easily generalize to a large varieties of rules. Still there are many questions:

Is there a more explicit formulation of construction method?
Is a helpful script available?

Here is an alternative construction that uses some linear algebra:

Let the desired period be n. We will focus on the special case n=4. First we will construct a wick of period 4. Let c(i) represent the presence of a replicator at (i, 0) at T=0 (1=present, 0=absent). Then the period-4 condition becomes c(i-4) + c(i) + c(i+4) = 0 (mod 2). Rearranging gives c(i) = c(i-4) + c(i-8) (mod 2). Thus, given a sequence c(0) through c(7), we can extend it into a doubly infinite sequence in a unique way.

Moreover, this sequence must be periodic, since the vector (c(i+1), ..., c(i+8)) is a linear function of (c(i), ..., c(i+7)), and this function is invertible. Thus, under repeated application of that function, the vector (c(0), ..., c(7)) must eventually go back to itself. That is, c is periodic. So the resulting pattern is a wick.

Now pick this length-2n "strip":

Code: Select all

x = 8, y = 2, rule = B2ae/SSuper
MBMBMBMB$MBMBMBMB!

Extending gives:

Code: Select all

x = 32, y = 8, rule = B2ae/SSuper
MBMBMBMB4.MBOBOBMB4.MBOBOBMB$MBMBMBMB4.MBOBOBMB4.MBOBOBMB5$13.A2.M.M
5.M.M.A$14.A.M.M5.M.M2.A!

Because the initial strip is gutter-symmetric, the wick is also gutter-symmetric. Two axes of symmetry have been marked in state 15 in the pattern above. Now, consider what lies between these two axes. We get a period-n oscillator, except that it will grow extra replicators at the edge which need to be supressed:

Code: Select all

x = 13, y = 2, rule = B2ae/SSuper
FM.M5.M.MF$FM.M5.M.MF!

Now add duoplets to supress the extra replicators, and you're ready to go.

Here's the same process applied to n=10:

Code: Select all

x = 229, y = 13, rule = B2ae/SSuper
G.G.G.G.G.G.G.G.G.G5.G.G3.G7.G5.G5.G3.G11.G3.G5.G5.G7.G3.G.G5.G.G.G.G
.G.G.G.G.G.G5.G.G3.G7.G5.G5.G3.G11.G3.G5.G5.G7.G3.G.G5.G.G.G.G.G.G.G.
G.G.G5.G$G.G.G.G.G.G.G.G.G.G5.G.G3.G7.G5.G5.G3.G11.G3.G5.G5.G7.G3.G.G
5.G.G.G.G.G.G.G.G.G.G5.G.G3.G7.G5.G5.G3.G11.G3.G5.G5.G7.G3.G.G5.G.G.G
.G.G.G.G.G.G.G5.G10$7.A2.G.G.G.G.G5.G.G3.G7.G5.G5.G3.G11.G3.G5.G5.G7.
G3.G.G5.G.G.G.G.G.A$8.A.G.G.G.G.G5.G.G3.G7.G5.G5.G3.G11.G3.G5.G5.G7.G
3.G.G5.G.G.G.G.G2.A!

Edit: here's an earlier draft of this post that was lost due to my browser crashing:

Ideas like this (for Margolus-emulating rules) and this (for Wolfram's Rule 150-emulating rules) could easily generalize to a large varieties of rules. Still there are many questions:

Is there a more explicit formulation of construction method?
Is a helpful script available?

Here is an alternative construction that uses some linear algebra:

Let the desired period be n. We will focus on the special case n=4. First we will construct a wick of period 4. Let c(i) represent the presence of a replicator at (i, 0) at T=0 (1=present, 0=absent). Then the period-4 condition becomes c(i-4) + c(i) + c(i+4) = 0 (mod 2). Rearranging gives c(i) = c(i-4) + c(i-8) (mod 2). Thus, given a sequence c(0) through c(7), we can extend it into a doubly infinite sequence in a unique way.

Moreover, this sequence must be periodic, since the vector (c(i+1), ..., c(i+8)) is a linear function of (c(i), ..., c(i+7)), and this function is invertible. Thus, under repeated application of that function, the vector (c(0), ..., c(7)) must eventually go back to itself. That is, c is periodic. So the resulting pattern is a wick.

Now pick this length-2n "strip":

Code: Select all

x = 8, y = 2, rule = B2ae/SSuper
MBMBMBMB$MBMBMBMB!

Extending gives:

Code: Select all

x = 32, y = 8, rule = B2ae/SSuper
MBMBMBMB4.MBOBOBMB4.MBOBOBMB$MBMBMBMB4.MBOBOBMB4.MBOBOBMB5$13.A2.M.M
5.M.M.A$14.A.M.M5.M.M2.A!

Because the initial strip is gutter-symmetric, the wick is also gutter-symmetric. Two axes of symmetry have been marked in state 15 in the pattern above. Now, consider what lies between these two axes. We get a period-n oscillator, except that it will grow extra replicators at the edge which need to be supressed:

[pzq_alex]

Here's a helper script

oscfinder.py.txt

(825 Bytes) Downloaded 49 times

[pzq_alex]

For W150 + constant dead cells:

W150WithBorder.rule

(172 Bytes) Downloaded 50 times

w150finder.py.txt

(396 Bytes) Downloaded 50 times

[GUYTU6J]

For W150 + constant dead cells:
W150WithBorder.rule
w150finder.py.txt

Excellent! The assisted W150 can instead be written as follows:

Code: Select all

@RULE W150WithBorder

State 1 follows Wolfram's Rule 150 (C' = W XOR C XOR E),
state 2 is a border treated as eternal state 0

@TABLE
n_states: 3
neighborhood: oneDimensional
symmetries: none

# C,W,E,C'
1,1,0,0
0,1,0,1
1,0,1,0
0,0,1,1
1,2,1,0
1,1,2,0
0,2,1,1
0,1,2,1

A period-5 oscillator:

Code: Select all

x = 33, y = 6, rule = B2a/S01e5i
3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2$ob2ob4o4bo2bo2bo4b4ob2o$2b2ob4o4bo2bo
2bo4b4ob2obo2$2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo!

Now, an unfortunate piece of news. The assisted W90 described in this way results in a rule that is actually capable of supporting odd-period oscillators, not only even ones:

Code: Select all

x = 316, y = 71, rule = W90WithBorder
BA.B10$B.2A.B10$B.A3.B10$BA.A.3A.2A4.3A3.2A6.2A3.3A4.2A.3A.A.AB10$BA.
A.A5.A7.A5.A.A.AB10$B3.2A3.B10$BA.A.A.A9.A.A.A.AB10$BA.A.A.A.3A.3A.2A
3.2A.A2.A2.A.A2.2A4.2A3.A.A.A2.2A.A3.A.3A.A3.A2.2A6.2A3.A2.A.4A.3A.3A
3.2A2.A.4A4.5A5.6A3.4A3.2A2.2A10.2A2.2A3.4A3.6A5.5A4.4A.A2.2A3.3A.3A.
4A.A2.A3.2A6.2A2.A3.A.3A.A3.A.2A2.A.A.A3.2A4.2A2.A.A2.A2.A.2A3.2A.3A.
3A.A.A.A.AB!
@RULE W90WithBorder

State 1 follows Wolfram's Rule 90 (C' = W XOR E),
state 2 is a border treated as eternal state 0

@TABLE
n_states: 3
neighborhood: oneDimensional
symmetries: none

# C,W,E,C'
1,1,1,0
0,1,0,1
1,0,0,0
0,0,1,1
1,2,0,0
1,0,2,0
0,2,1,1
0,1,2,1

Our familiar B2ae/S is only suitable for even-period oscillators where isolated domino replicators does not contact. This is a limitation on B2ae/S, not an inherent property of Rule 90. (EDIT: B2ae/S is better said as simulating Rule 18, where C' = (NOT C) AND (W XOR E). ) To cover all periods we should choose this rule instead:

Code: Select all

x = 54, y = 6, rule = B2a/S03a
3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2$obobob3ob2o4b3o3b
2o6b2o3b3o4b2ob3obobo$2bobob3ob2o4b3o3b2o6b2o3b3o4b2ob3obobobo2$2bo2bo
2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo!

Therefore, the first oscfinder.py script needs a remake to allow for odd periods. (EDIT: Because it seems to assume that the parity of replicators is the same.)

[pzq_alex]

Therefore, the first oscfinder.py script needs a remake to allow for odd periods.

Surprisingly, it does not. Simply remove the assert statement and it'll be ready to go. Alternatively, generate an osc of period 2x and downscale by 2.

[GUYTU6J]

Demonstration for rules that are covered by the scheme of thread. EVEN means that the cellular automata has an oscillator for any even period, ALL means that the cellular automata has an oscillator for any period (omniperiodic). Note that rules with EVEN does not necessarily inhibit odd-period oscillators, whose existence may be based on other mechanisms.

• Bugs (B3567/S15678) and Diamoeba (B35678/S5678): EVEN. As mentioned in this post, a dot supported by a period-2 edge replicates following Wolfram's Rule 18.

  Code: Select all

  x = 38, y = 38, rule = B3567/S15678History
  3.B.AC$2.4ABD$.B6AD$8ABD$.9AD$B9ABD$.11AD$2.B9ABD$3.11AD$4.B9ABD$5.
  11AD$6.B9ABD$7.11AD6.D$8.B9ABD4.D$9.11AD2.D$10.B9AB2D$11.11AD$12.B9AB
  D$13.11AD$14.B9ABD$15.11AD$16.B9ABD$17.11AD$18.B9ABD$19.11AD$20.B9ABD
  $21.11AD$22.B9ABD$23.11AD$24.B9ABD$25.11AD$26.B9ABC$27.11A$28.B8A$29.
  8AB$30.B6A$31.4AB$32.B.A!
  

• Maze with Mice (B37/S12345) and Mazectric with Mice (B37/S1234): EVEN. A dot supported by a tube replicates following Wolfram's Rule 18.

  Code: Select all

  x = 18, y = 9, rule = B37/S1234History
  2.A.A.A.A.A.A2.A$2.A.A.A.A.A.A2.A2$18A$.C15D$18A2$2.A2.A.A.A.A.A.A$2.
  A2.A.A.A.A.A.A!
  

• LongLife (B345/S5) and Gems (B34578/S456): EVEN. In the following p2 phoenix-supported pattern, a full domino in the first two rows replicates following Wolfram's Rule 18.

  Code: Select all

  x = 20, y = 5, rule = B345/S5History
  2.CDCDCDCDCDCDCDCD$.BC15DA$ABABABABABABABABABAB$BABABABABABABABABABA$
  .ABABABABABABABABAB!
  

• Day and Night (B3678/S34678): EVEN. A dot supported by an edge replicates following Wolfram's Rule 18.

  Code: Select all

  x = 20, y = 20, rule = B3678/S34678History
  .2A.C$.2ABAD$5A.D$7AD$2.5A.D$2.7AD$4.5A.D$4.7AD$6.5A.D$6.7AD$8.5A.D$
  8.7AD$10.5A.D$10.7AD$12.5A.D$12.7AD$14.5A$14.6A$16.4A$16.2A!
  

  See also the relevant section from David Bell's article:

  Code: Select all

  Dean Hickerson discovered several classes of oscillators which emulate a
  1-D XOR cellular automaton.  In this automaton the universe consists of a
  line of cells, where each cell is in one of the states 0 or 1; any two 1s
  are an even distance apart.  (The 1s are confined to even positions in
  even generations and odd positions in odd generations.)  Each generation,
  the new state of each cell is the XOR of the previous states of its two
  neighbors.  For a finite universe, you assume that the cells beyond the
  end cells are permanently 0.  In Day & Night, a diagonal strip of cells
  in one of these oscillators changes state in the same manner as the
  corresponding 1-D XOR oscillator.  It is easy to prove that 1-D XOR
  oscillators can have any even period; therefore oscillators of all even
  periods exist in Day & Night as well.
  
  For example, the line of 16 cells below becomes its mirror image after
  5 generations, so it has period 10:
  
      gen 0:   0101010001000000
      gen 1:   1000001010100000
      gen 2:   0100010000010000
      gen 3:   1010101000101000
      gen 4:   0000000101000100
      gen 5:   0000001000101010
  
  
  The following figure shows examples of the most versatile class of these
  oscillators.  The first emulates the p10 shown above; the second has
  period 62 and a rotor of size 10.  (The "rotor" of any oscillator is the
  set of all cells that change state at some time.)  The presence or absence
  of "steps" along the diagonal represents the cells of the 1-D automaton,
  where the presence of a step is the state 1 and an absence of a step is
  the state 0.  Each generation, the cells making up the steps are present
  if and only if exactly one of their two adjacent steps was present in the
  previous generation (except at the two ends).
  
   ...OO..........................OO.............
   ...OO..........................OO.............
   ..OOOO........................OOOO............
   .O....OO.....................O....O...........
   .OO..O.O.....................OO..O.OO.........
   OO..O.O.OO..................OO..O.O.O.........
   .O.OO..O.O...................O.OO..O.O........
   .O.OO...O.OO.................O.OO...O.O.......
   OO.......O.O................OO.......O.O......
   OO........O.O...............OO........O.O.....
   ...........O.O.........................O.O....
   ............O.OO........................O.O...
   .............O.O.........................O.O..
   ..............O.O.....................OOO..OOO
   ...............O.O....................OO...OOO
   ................O.O......................O.O..
   .................O.O................OOOOOOO...
   ..................O.O...............OO..O.....
   ...................O.O........................
   ................OOO..OOO......................
   ................OO...OOO......................
   ...................O.O........................
   ..............OOOOOOO.........................
   ..............OO..O...........................
  
  [Figure 41.  Period 10 and period 62 1-D XOR cellular automaton emulators (DH)]
  

• Vote 4/5 (B4678/S35678): ALL. A dot supported by a 2-cell thick line replicates following Wolfram's Rule 150.

  Code: Select all

  #C A period-9 oscillator in Vote 4/5.
  #C The D8 symmetric design is to prevent corner cells from dying.
  x = 133, y = 133, rule = B4678/S35678
  7b2o4b6obo2b2o2b4ob2o2bo4b2o2b2obo6b4o2b11o2b4o6bob2o2b2o4bo2b2ob4o2b
  2o2bob6o4b2o$b131o$b131o$b2o127b2o$b2o127b2o$b2o127b2o$b2o127b2o$3o
  127b3o$3o127b3o$b2o127b2o$b2o127b2o$b2o127b2o$b2o127b2o$3o127b3o$3o
  127b3o$3o127b3o$3o127b3o$3o127b3o$3o127b3o$b2o127b2o$3o127b3o$b2o127b
  2o$b2o127b2o$3o127b3o$3o127b3o$b2o127b2o$b2o127b2o$3o127b3o$3o127b3o$
  3o127b3o$3o127b3o$b2o127b2o$3o127b3o$3o127b3o$b2o127b2o$b2o127b2o$3o
  127b3o$b2o127b2o$b2o127b2o$b2o127b2o$b2o127b2o$3o127b3o$3o127b3o$b2o
  127b2o$b2o127b2o$3o127b3o$3o127b3o$b2o127b2o$3o127b3o$b2o127b2o$b2o
  127b2o$b2o127b2o$b2o127b2o$b2o127b2o$b2o127b2o$3o127b3o$3o127b3o$3o
  127b3o$3o127b3o$b2o127b2o$b2o127b2o$3o127b3o$3o127b3o$3o127b3o$3o127b
  3o$3o127b3o$3o127b3o$3o127b3o$3o127b3o$3o127b3o$3o127b3o$3o127b3o$b2o
  127b2o$b2o127b2o$3o127b3o$3o127b3o$3o127b3o$3o127b3o$b2o127b2o$b2o127b
  2o$b2o127b2o$b2o127b2o$b2o127b2o$b2o127b2o$3o127b3o$b2o127b2o$3o127b3o
  $3o127b3o$b2o127b2o$b2o127b2o$3o127b3o$3o127b3o$b2o127b2o$b2o127b2o$b
  2o127b2o$b2o127b2o$3o127b3o$b2o127b2o$b2o127b2o$3o127b3o$3o127b3o$b2o
  127b2o$3o127b3o$3o127b3o$3o127b3o$3o127b3o$b2o127b2o$b2o127b2o$3o127b
  3o$3o127b3o$b2o127b2o$b2o127b2o$3o127b3o$b2o127b2o$3o127b3o$3o127b3o$
  3o127b3o$3o127b3o$3o127b3o$3o127b3o$b2o127b2o$b2o127b2o$b2o127b2o$b2o
  127b2o$3o127b3o$3o127b3o$b2o127b2o$b2o127b2o$b2o127b2o$b2o127b2o$b131o
  $b131o$7b2o4b6obo2b2o2b4ob2o2bo4b2o2b2obo6b4o2b11o2b4o6bob2o2b2o4bo2b
  2ob4o2b2o2bob6o4b2o!
  

[muzik]

Flock has a XOR-like 1D mechanism as follows, which could potentially be used to prove some extent of omniperiodicity in a supporting rule range:

Looks like there's a family of oscillators which mimic a 1D CA.

Code: Select all

x = 25, y = 8, rule = B3/S12
2bobobobobobobobobobobo$2bobobobobobobobobobobo$22bobo$19bo2bobo$obo
16bo$obo$2bobobobobobobobobobobo$2bobobobobobobobobobobo!

[pzq_alex]

Flock has a XOR-like 1D mechanism as follows, which could potentially be used to prove some extent of omniperiodicity in a supporting rule range:

Looks like there's a family of oscillators which mimic a 1D CA.

Code: Select all

x = 25, y = 8, rule = B3/S12
2bobobobobobobobobobobo$2bobobobobobobobobobobo$22bobo$19bo2bobo$obo
16bo$obo$2bobobobobobobobobobobo$2bobobobobobobobobobobo!

Isn't that just W90 but restricted to a single parity? Those should allow all multiples of 6 as periods.

[Haycat2009]

Can W22 be used to prove omniperiodicity?

[actinophrys]

Ideas like this (for Margolus-emulating rules) and this (for Wolfram's Rule 150-emulating rules) could easily generalize to a large varieties of rules.

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.

[Sokwe]

Ideas like this (for Margolus-emulating rules) and this (for Wolfram's Rule 150-emulating rules) could easily generalize to a large varieties of rules.

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!

Arbitrarily choosing the complete history of two adjacent cells uniquely determines the (infinite) pattern in generation 0:

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!

Edit: Fixing the proof of all even periods in 2x2 (B36/S125)?

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.

[yujh]

A bit off-topic, but the above proof also seems to be applicable to spaceships that operate under similar mechanisms, such as those found at (specifically the ) viewtopic.php?f=11&t=6352&p=224679#p224679
One can use this for the construction of the start of the ship:

Code: Select all

x = 4, y = 8, rule = W90History
2.2D$2.DC$.2D$.2D$.DC$2D$2D$DC!

It would then force the back of the ship as so, marked in yellow:

Code: Select all

x = 5, y = 8, rule = W90History
2.3D$2.EDC$.3D$.3D$.EDC$3D$3D$EDC!

This should show that all ships with speeds xc/p with x, p same parity, and 3x < p or x = 1, p = 3 (and i believe one can show that other speeds are impossible?)

As an example,

Code: Select all

x = 19, y = 12, rule = W90History
3.D.C.C8.C.C$4.E.D.D6.C$3.D.C.D8.C$2.D.C.C8.C.C$3.E.D.D6.C$2.D.C.D8.C
$.D.C.C8.C.C$13.C$14.C$13.C.C$12.C!

=>

Code: Select all

x = 7, y = 3, rule = B2c3aq4acjqr5ackq6ac7e/S1e2-ae3aejnr4cijqrwy5aeiq6ek8
b6o$obobo$b5o!

[pzq_alex]

Actually, the proof method above is implicit in this post (about 3 years ago) of mine; said post also contains a custom rule to help implement this strategy, and also an extension to replicator-based spaceships. What is missing in this theory is an investigation of the smallest oscillator/spaceship realizing a given period/speed; in this oscillator case this should be doable with some finite field theory, but I'm less sure about spaceships. In any case my time is too much occupied by real Life to think about these things...

A bit off-topic, but the above proof also seems to be applicable to spaceships that operate under similar mechanisms, such as those ...

[qqd]

All outer totalistic rules from B4/S235 to B4678/S01235678 are omniperiodic (a total of 256 rules) because all of them have this W150 emulator that can be fenced by always-on or always-off cells:

Code: Select all

x = 74, y = 33, rule = B4/S235
3o7b2o8bobo7bo10b2o8bo10bo$3o7b3o7b3o7b3o7b3o7b3o7b3o7b3o$12bo8bo9b2o
7bo9bobo7b2o8b3o8$o9b3o7b3o7bo9b3o7bo9bo9b3o$o9bobo7bobo7bo9bobo7bo9b
o9bobo$o9b3o7b3o7bo9b3o7bo9bo9b3o18$b72o$74o$o72bo!

This also encompasses all INT rules from B4a/S2a3aij5iqy to B2-ac3-ai45-i678/S01234-a5678 (Based on an identification by catalogue of a p56 oscillator in this rule that triggers all the W150 transitions).