Omniperiodicity based on XOR replicators
-
- Posts: 2200
- Joined: August 5th, 2016, 10:27 am
- Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
- Contact:
Omniperiodicity based on XOR replicators
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!
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!
Re: Omniperiodicity based on XOR replicators
Here is an alternative construction that uses some linear algebra:GUYTU6J wrote: ↑November 18th, 2022, 12:50 amIdeas 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?
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!
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!
Code: Select all
x = 13, y = 2, rule = B2ae/SSuper
FM.M5.M.MF$FM.M5.M.MF!
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!
Here is an alternative construction that uses some linear algebra:GUYTU6J wrote: ↑November 18th, 2022, 12:50 amIdeas 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?
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":Extending gives:Code: Select all
x = 8, y = 2, rule = B2ae/SSuper MBMBMBMB$MBMBMBMB!
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 = 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!
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
Re: Omniperiodicity based on XOR replicators
Here's a helper script
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
Re: Omniperiodicity based on XOR replicators
For W150 + constant dead cells:
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
-
- Posts: 2200
- Joined: August 5th, 2016, 10:27 am
- Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
- Contact:
Re: Omniperiodicity based on XOR replicators
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
Code: Select all
x = 33, y = 6, rule = B2a/S01e5i
3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2$ob2ob4o4bo2bo2bo4b4ob2o$2b2ob4o4bo2bo
2bo4b4ob2obo2$2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo!
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
Code: Select all
x = 54, y = 6, rule = B2a/S03a
3bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2$obobob3ob2o4b3o3b
2o6b2o3b3o4b2ob3obobo$2bobob3ob2o4b3o3b2o6b2o3b3o4b2ob3obobobo2$2bo2bo
2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo2bo!
Last edited by GUYTU6J on November 25th, 2022, 4:51 am, edited 1 time in total.
熠熠种花 - Glimmering Garden
Harvest Moon
2-engine p45 gliderless HWSS gun
Small p2070 glider gun
Forgive me if I withhold my enthusiasm.
Harvest Moon
2-engine p45 gliderless HWSS gun
Small p2070 glider gun
Forgive me if I withhold my enthusiasm.
Re: Omniperiodicity based on XOR replicators
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"?
How much of current CA technology can I redevelop "on a desert island"?
-
- Posts: 2200
- Joined: August 5th, 2016, 10:27 am
- Location: 拆哪!I repeat, CHINA! (a.k.a. 种花家)
- Contact:
Re: Omniperiodicity based on XOR replicators
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.
See also the relevant section from David Bell's article:
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!
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!
熠熠种花 - Glimmering Garden
Harvest Moon
2-engine p45 gliderless HWSS gun
Small p2070 glider gun
Forgive me if I withhold my enthusiasm.
Harvest Moon
2-engine p45 gliderless HWSS gun
Small p2070 glider gun
Forgive me if I withhold my enthusiasm.
Re: Omniperiodicity based on XOR replicators
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 pmLooks 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!
Help wanted: How can we accurately notate any 1D replicator?
Re: Omniperiodicity based on XOR replicators
Isn't that just W90 but restricted to a single parity? Those should allow all multiples of 6 as periods.muzik wrote: ↑January 14th, 2023, 1:11 pmFlock 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 pmLooks 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!
\sum_{n=1}^\infty H_n/n^2 = \zeta(3)
How much of current CA technology can I redevelop "on a desert island"?
How much of current CA technology can I redevelop "on a desert island"?
-
- Posts: 738
- Joined: April 26th, 2023, 5:47 am
- Location: Bahar Junction, Zumaland
Re: Omniperiodicity based on XOR replicators
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.
Also, support Conway and Friends story mode!
I mean no harm to those who have tested me. But do not take this for granted.