Replicator-based technology

[pzq_alex]

(Yep, this is The One Replicator Thread To Rule Them All. For previous, rather short-lived threads on this matter, see viewtopic.php?p=153774 and viewtopic.php?p=123679. )

Anyway, I've come with a new tool for constructing replicator-based oscillators and spaceships, that is Rule:FeynmanDiagramGen. (Disclaimer: it only works for 1D replicators following Rule 90. Whenever I talk about Rule 90, I assume a parity-constrained pattern. )

Oscillator
Pick any even number p and I'll construct an oscillator in bounded grid (specifically the :Px,y flavor) Rule 90 with period p.
For example, take p=8. Then draw a 2x8 rectangle like so:

Code: Select all

x = 2, y = 8, rule = FeynmanDiagramGen:T0,8
2C$2C$2C$2C$2C$2C$2C$CD!

And run it until it repeats. The repeating component is:

Code: Select all

x = 13, y = 8, rule = FeynmanDiagramGen:T0,8
8AB4A$7ABAB3A$6AB3AB2A$5ABABABABA$4AB8A$3ABAB7A$2AB3AB6A$ABABABAB5A!

This is the so-called Feynman diagram (hence the rule name) for the p8 oscillator -- which is basically the phases of the oscillator laid down vertically. Transcribing the result into a rule such as B2ae/S gives:

Code: Select all

x = 17, y = 2, rule = B2ae/S
o9bo4bo$bo8bo5bo!

The second column can actually be pretty much anything (so far as it's parity-constrained); the only restriction is that the first column is empty and the second column does not have some subperiod (with respect to space).

Spaceship
Given two number k and p, such that k/p<=1/3, and k+p is even, I'll construct a kc/p spaceship.
To illustrate this with an example, take k=2, p=8. We can construct a "strip" in a :T10000-k,p torus as follows:

Code: Select all

x = 3, y = 8, rule = FeynmanDiagramGen:T1000-2,8
2C$2C$2C$2C$CD$.2C$.2C$.CD!
[[ ZOOM 25 ]]

The restriction to the stripe is that a) it must consist of k rectangles, b) each of which has width 2 and only the lower-right cell is state 4, and c) each rectangle must have length of at least 3.
Running that, we see the repeating component is:

Code: Select all

x = 55, y = 8, rule = FeynmanDiagramGen:T1000-2,8
5ABAB3AB3ABAB5ABAB5AB3AB3AB5ABABABAB3A$4AB3ABABABAB3AB3AB3AB3ABABABAB
ABAB3AB7AB2A$3ABABAB7ABABABABABABABAB11ABABAB5ABABA$2AB5AB5AB15AB9AB
5AB3AB4A$ABAB3ABAB3ABAB13ABAB7ABAB3ABABABAB3A$.3ABAB3ABAB3AB11AB3AB5A
B3ABAB7AB2A$.2AB3ABAB3ABABAB9ABABABAB3ABABAB3AB5ABABA$.ABABAB3ABAB5AB
7AB7ABAB5ABABAB3AB3AB!
[[ ZOOM 9 ]]

Transcribing the result:

Code: Select all

x = 56, y = 3, rule = B2c3a6ac7e/S1e2cik3ejnr4i
2b53o$bo4bobo3bo3bobo5bobo5bo3bo3bo5bobobobo2bo$55o!

Very easy!

[pipsqueek]

but there is a much smaller spaceship of the same speed

Code: Select all

x = 9, y = 3, rule = B2c3a6ac7e/S1e2cik3ejnr4i
b7o$3bo4bo$8o!

[pzq_alex]

but there is a much smaller spaceship of the same speed

Code: Select all

x = 9, y = 3, rule = B2c3a6ac7e/S1e2cik3ejnr4i
b7o$3bo4bo$8o!

Yes, but its Feynman diagram looks like this:

Code: Select all

x = 1002, y = 10, rule = FeynmanDiagramGen:T1000-2,8
$497.2AB4A$497.ABAB3A$498.3AB2A$498.2ABABA$498.AB3AB$499.3ABA$499.2AB
ABA$499.AB3AB!

And its left edge does not line up with its right edge, and therefore it cannot tile the plane. That is a necessary and sufficient condition for a spaceship to occur in my method.
(A general spaceship of a specific speed is much more annoying to deal with than a general oscillator due to the varying shapes its Feynman diagram can take. )

Edit: ha, I was fooled. The problem comes from the nonstandard interaction at gen 4/5. That interaction at the tail could not have appeared in a "regular" spaceship without tubes. Translated into terms of Feynman diagrams:

Code: Select all

x = 8, y = 8, rule = FeynmanDiagramGen:T1000-2,8
3AB2A$2ABABA$AB3AB$.3ABA$.2ABABA$.AB3AB$.2AB4A$.ABAB3A!

The lower-left would've pulled the back end twice.

[pzq_alex]

I performed a bit of analysis on W90 oscilllators with constant-dead borders. Define the length of such an oscillator to be the distance between the two border cells. Let n be any positive integer, f(n) be the smallest length for a period-2n oscillator (note that I'm always talking about period-constrained W90). Barring any mistakes in my proofs, we have:

• f(2n) always equals 2f(n) (it's easy to see that it's at most 2f(n));
• for an odd number n, f(n) <= 2^d+1, where d is the multiplicative order of 2 mod n. More precisely, one can always construct an oscillator with length dividing either 2^d-1 or 2^d+1. However I believe in general f(n) can be smaller than this.

For instance, here is a period 46 (n=23) oscillator of length 2049

Code: Select all

x = 2054, y = 2, rule = B2ae/S
o25bobo3bo5bobobobobobo3bobobo5bobo3bobobobo3bobobo5bobobobobo7bobo3bo
bobo3bo3bo3bobobo3bo3bobobo3bobobobobobo3bo3bo5bobo7bo9bobo3bobobobobo
3bo5bo3bo3bobo5bobobo7bobo3bo7bobobo5bo3bo5bo3bo3bo7bo7bo5bobo3bobobob
obo5bobo3bo5bobobobo7bo3bobo3bo3bobobo7bo5bobo13bobobo7bo3bo9bo5bo3bob
obobobobo3bo7bo3bobobo3bo5bo7bo11bo3bo5bobo3bo3bo3bobo5bo5bobo3bo3bobo
3bo3bobobobobobo9bo5bo7bobo7bobo5bo3bobo3bo3bo3bo3bobo3bo3bo5bo15bo3bo
bo3bo3bo3bobo5bo3bo3bo7bo3bo3bobobobobobobo3bo3bobobo5bo3bobo5bo3bobob
o3bobo3bobo3bobobobobobobobo5bo7bobo3bobobobobobobo3bobo5bobo3bo5bobob
o5bo3bobo5bo5bobo7bo3bo15bo3bobobobo5bo3bo23bobobo3bobo3bo3bobobo5bobo
3bobo5bo5bobobobo9bobobobobobobo3bobobobobo7bobobo3bobobo3bobobobobo5b
obobobobobo5bo3bo3bobo3bobo3bobo5bobo5bo3bo3bo7bobo3bo3bo3bo7bo5bo3bob
obo3bobobo3bobo5bobo7bo3bobo3bobobobo3bobobo5bo5bobobobo3bo5bobo9bobob
obobo5bobobobobo3bo3bobo7bo3bo3bobobobo5bobo3bo3bobobobobobobobo5bobo
3bo3bobo5bobobobobobo11bo3bobo7bobo3bobo3bobobo3bo3bobo7bo3bo9bo5bobob
o3bobobobobo3bo3bobobobo19bo3bobobobo13bo5bobobobo3bo3bo3bobobobo15bob
obobobobobo3bobo5bobobo3bo7bo7bo11bobobobo3bobo3bobobo5bobo7bobobo3bo
3bobobo7bobobobo3bo7bo3bo5bobo3bobo3bo3bo3bobo13bo5bobobobobo3bo5bo3bo
bobobobo11bo3bo3bo5bo5bo5bobobo7bo5bobo3bo3bobobobo7bo3bobo9bobo3bobo
3bo9bo3bo15bobobo5bobo9bo9bobobobo5bobo5bobo3bo7bobobobobobo7bobobo3bo
bobo5bobo$bo24bobo3bo5bobobobobobo3bobobo5bobo3bobobobo3bobobo5bobobob
obo7bobo3bobobo3bo3bo3bobobo3bo3bobobo3bobobobobobo3bo3bo5bobo7bo9bobo
3bobobobobo3bo5bo3bo3bobo5bobobo7bobo3bo7bobobo5bo3bo5bo3bo3bo7bo7bo5b
obo3bobobobobo5bobo3bo5bobobobo7bo3bobo3bo3bobobo7bo5bobo13bobobo7bo3b
o9bo5bo3bobobobobobo3bo7bo3bobobo3bo5bo7bo11bo3bo5bobo3bo3bo3bobo5bo5b
obo3bo3bobo3bo3bobobobobobo9bo5bo7bobo7bobo5bo3bobo3bo3bo3bo3bobo3bo3b
o5bo15bo3bobo3bo3bo3bobo5bo3bo3bo7bo3bo3bobobobobobobo3bo3bobobo5bo3bo
bo5bo3bobobo3bobo3bobo3bobobobobobobobo5bo7bobo3bobobobobobobo3bobo5bo
bo3bo5bobobo5bo3bobo5bo5bobo7bo3bo15bo3bobobobo5bo3bo23bobobo3bobo3bo
3bobobo5bobo3bobo5bo5bobobobo9bobobobobobobo3bobobobobo7bobobo3bobobo
3bobobobobo5bobobobobobo5bo3bo3bobo3bobo3bobo5bobo5bo3bo3bo7bobo3bo3bo
3bo7bo5bo3bobobo3bobobo3bobo5bobo7bo3bobo3bobobobo3bobobo5bo5bobobobo
3bo5bobo9bobobobobo5bobobobobo3bo3bobo7bo3bo3bobobobo5bobo3bo3bobobobo
bobobobo5bobo3bo3bobo5bobobobobobo11bo3bobo7bobo3bobo3bobobo3bo3bobo7b
o3bo9bo5bobobo3bobobobobo3bo3bobobobo19bo3bobobobo13bo5bobobobo3bo3bo
3bobobobo15bobobobobobobo3bobo5bobobo3bo7bo7bo11bobobobo3bobo3bobobo5b
obo7bobobo3bo3bobobo7bobobobo3bo7bo3bo5bobo3bobo3bo3bo3bobo13bo5bobobo
bobo3bo5bo3bobobobobo11bo3bo3bo5bo5bo5bobobo7bo5bobo3bo3bobobobo7bo3bo
bo9bobo3bobo3bo9bo3bo15bobobo5bobo9bo9bobobobo5bobo5bobo3bo7bobobobobo
bo7bobobo3bobobo5bo2bo!

and one of length 2047:

Code: Select all

x = 2052, y = 2, rule = B2ae/S
o23bobo3bo11bo3bo7bobo5bo9bobobobobo5bobobo5bo3bobo3bo11bo11bo5bo5bob
o3bo5bobobobobo3bobo3bo3bo5bobobo5bo3bobobo3bobo3bobobo5bobo3bo3bobob
obobo3bobo7bobo3bobo9bobo5bobobo3bobobobobo5bo3bobobobobobobo7bobobo5b
o7bobobo9bo3bo5bo7bo7bo3bo3bo3bo5bo3bobo3bo3bobobobo3bobobo3bo3bobobo
3bobobo3bo7bo7bobo3bo3bo5bobo5bo3bo3bo3bobobo11bobobo3bobo3bobobo5bo5b
o3bo3bo3bo3bobobo3bo3bobobobobobo5bo5bobobobobobobobo7bobo7bobo3bobo3b
o7bo3bo9bo5bobobobo9bobo3bo5bo3bobobo3bo9bo9bo5bobobo3bobo3bo3bobo9bo
bo5bo3bobobobobobo3bobo5bobo3bobo5bobobobo3bobo3bobo7bobo5bo3bobobobo
bobobobobo3bobobobo3bobo9bobo5bobo3bo9bobo3bo3bo7bo3bo7bobobobo3bobob
o7bobobo7bo3bobobobo3bobo5bo5bo3bobobo3bo3bo3bobo3bobobobo5bo3bo3bo3b
obobo3bo3bo5bobo3bo7bo7bobo5bo5bo3bobo3bobobo3bobo5bo7bo3bobobobobo3b
obo5bobo3bobo3bo3bobo3bobobobo3bobobo3bo17bobo5bobo3bo3bobobo5bo11bo3b
o3bobo3bo3bo3bo3bo7bobobobo3bobo3bobobo3bo17bobobobo5bo3bobobo9bobobo
bobobo3bobo3bobo7bobo3bobo5bobobobo7bo5bo7bobo5bo3bobobo3bobobo3bo3bo
5bobo5bo7bobo3bobobobo7bobo3bo5bo3bobobo5bo3bobobo5bo3bobo13bo3bo11bo
bobobobo3bobo11bobobobo5bo5bobo3bo3bobobobo7bo5bo11bo3bobo5bo3bobobob
obo7bo3bo3bobobo5bobobobobobo5bobo11bo3bo3bobo3bobo3bobobobobobobobo3b
obo3bo5bobobobobo5bo3bo3bo5bobobobobobo3bo9bobo5bo5bobobobobo5bobo7bo
bobo9bobo7bobo9bo3bobo3bo5bo9bo3bo3bobobo3bo3bobobobo5bo3bo9bobobobo15b
obobobobo3bo2bo$bo22bobo3bo11bo3bo7bobo5bo9bobobobobo5bobobo5bo3bobo3b
o11bo11bo5bo5bobo3bo5bobobobobo3bobo3bo3bo5bobobo5bo3bobobo3bobo3bobo
bo5bobo3bo3bobobobobo3bobo7bobo3bobo9bobo5bobobo3bobobobobo5bo3bobobo
bobobobo7bobobo5bo7bobobo9bo3bo5bo7bo7bo3bo3bo3bo5bo3bobo3bo3bobobobo
3bobobo3bo3bobobo3bobobo3bo7bo7bobo3bo3bo5bobo5bo3bo3bo3bobobo11bobob
o3bobo3bobobo5bo5bo3bo3bo3bo3bobobo3bo3bobobobobobo5bo5bobobobobobobo
bo7bobo7bobo3bobo3bo7bo3bo9bo5bobobobo9bobo3bo5bo3bobobo3bo9bo9bo5bob
obo3bobo3bo3bobo9bobo5bo3bobobobobobo3bobo5bobo3bobo5bobobobo3bobo3bo
bo7bobo5bo3bobobobobobobobobo3bobobobo3bobo9bobo5bobo3bo9bobo3bo3bo7b
o3bo7bobobobo3bobobo7bobobo7bo3bobobobo3bobo5bo5bo3bobobo3bo3bo3bobo3b
obobobo5bo3bo3bo3bobobo3bo3bo5bobo3bo7bo7bobo5bo5bo3bobo3bobobo3bobo5b
o7bo3bobobobobo3bobo5bobo3bobo3bo3bobo3bobobobo3bobobo3bo17bobo5bobo3b
o3bobobo5bo11bo3bo3bobo3bo3bo3bo3bo7bobobobo3bobo3bobobo3bo17bobobobo
5bo3bobobo9bobobobobobo3bobo3bobo7bobo3bobo5bobobobo7bo5bo7bobo5bo3bo
bobo3bobobo3bo3bo5bobo5bo7bobo3bobobobo7bobo3bo5bo3bobobo5bo3bobobo5b
o3bobo13bo3bo11bobobobobo3bobo11bobobobo5bo5bobo3bo3bobobobo7bo5bo11b
o3bobo5bo3bobobobobo7bo3bo3bobobo5bobobobobobo5bobo11bo3bo3bobo3bobo3b
obobobobobobobo3bobo3bo5bobobobobo5bo3bo3bo5bobobobobobo3bo9bobo5bo5b
obobobobo5bobo7bobobo9bobo7bobo9bo3bobo3bo5bo9bo3bo3bobobo3bo3bobobob
o5bo3bo9bobobobo15bobobobobo3bobo!

When I get time I'll post the proofs of these results; for a brief summary, they use the Feynman diagram perspective above to translate the problem into something about a linear recurrence in the ring F_2[t]/(t^n-1), and then use the Chinese Remainder Theorem and finite field theory. Perhaps the expert reader will be able to reverse-engineer the construction in the second bullet point from the oscillators above...

[Sokwe]

I performed a bit of analysis on W90 oscilllators with constant-dead borders.... When I get time I'll post the proofs of these results; for a brief summary, they use the Feynman diagram perspective above to translate the problem into something about a linear recurrence in the ring F_2[t]/(t^n-1), and then use the Chinese Remainder Theorem and finite field theory.

Nice! Presumably something similar could be done for rules 105 and 150, as they also have the property that setting an arbitrary history for 2 adjacent cells uniquely determines the full infinite pattern. You could likewise do the same analysis with an always-on border in rule 90. However, if the length of the oscillator is already a multiple of 3, then you can simply add (mod 2) the stable pattern (2 off cells, 1 on cell) in rule 90 to flip the always-off cell to always-on. Rules 105 and 150 are their own black-white reversals, so we can get always-on boundaries from always-off boundaries simply flipping the state of the entire pattern.