Omniperiodicity based on XOR replicators

For discussion of other cellular automata.
Post Reply
GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Omniperiodicity based on XOR replicators

Post by GUYTU6J » November 18th, 2022, 12:50 am

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!

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: Omniperiodicity based on XOR replicators

Post by pzq_alex » November 18th, 2022, 4:08 am

GUYTU6J wrote:
November 18th, 2022, 12:50 am
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:
GUYTU6J wrote:
November 18th, 2022, 12:50 am
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:
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: Omniperiodicity based on XOR replicators

Post by pzq_alex » November 19th, 2022, 3:54 am

Here's a helper script
oscfinder.py.txt
(825 Bytes) Downloaded 23 times
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: Omniperiodicity based on XOR replicators

Post by pzq_alex » November 25th, 2022, 1:46 am

For W150 + constant dead cells:
W150WithBorder.rule
(172 Bytes) Downloaded 21 times
w150finder.py.txt
(396 Bytes) Downloaded 22 times
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: Omniperiodicity based on XOR replicators

Post by GUYTU6J » November 25th, 2022, 4:02 am

pzq_alex wrote:
November 25th, 2022, 1:46 am
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.)
Last edited by GUYTU6J on November 25th, 2022, 4:51 am, edited 1 time in total.

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: Omniperiodicity based on XOR replicators

Post by pzq_alex » November 25th, 2022, 4:21 am

GUYTU6J wrote:
November 25th, 2022, 4:02 am
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.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

GUYTU6J
Posts: 2200
Joined: August 5th, 2016, 10:27 am
Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
Contact:

Re: Omniperiodicity based on XOR replicators

Post by GUYTU6J » November 27th, 2022, 1:26 pm

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!
    

User avatar
muzik
Posts: 5614
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Omniperiodicity based on XOR replicators

Post by muzik » January 14th, 2023, 1:11 pm

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:
velcrorex wrote:
January 28th, 2016, 7:39 pm
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!

User avatar
pzq_alex
Posts: 792
Joined: May 1st, 2021, 9:00 pm
Location: tell me if you know

Re: Omniperiodicity based on XOR replicators

Post by pzq_alex » January 15th, 2023, 12:27 am

muzik wrote:
January 14th, 2023, 1:11 pm
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:
velcrorex wrote:
January 28th, 2016, 7:39 pm
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.
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)

How much of current CA technology can I redevelop "on a desert island"?

Haycat2009
Posts: 738
Joined: April 26th, 2023, 5:47 am
Location: Bahar Junction, Zumaland

Re: Omniperiodicity based on XOR replicators

Post by Haycat2009 » February 8th, 2024, 10:32 pm

Can W22 be used to prove omniperiodicity?
~ Haycat Durnak, a hard-working editor
Also, support Conway and Friends story mode!
I mean no harm to those who have tested me. But do not take this for granted.

Post Reply