User:Pzq Alex/Replicator

(Note: this was originally intended to be a forum post, but I prefer not to save drafts on the forums (as saving multiple draft versions of the same post creates multiple drafts), so it's here on the wiki instead. )

This post (hopefully) demystifies the theory behind those oscillators and spaceships based on replicators. These include the "replicators in a tube oscillators" (e.g. B2ae/S), "Basilisk-type spaceships" (e.g. Basilisk), and the Margolus rule emulated by B3/S5.

Terminology

All replicators are assumed to be 1D replicators that are unit cells of W90 or W150. One cell in the emulated rule is called a "unit" length in the original rule (emulator rule?). In addition, we assume three additional types of constructs:

• A "blocker", which prevents any replicators from being spawned on its place;
• A "push", when a replicator is behind it, moves forward one unit.
• A "pull", when a replicator is in front of it, moves forward one unit.

Obviously, an oscillator will require blockers at either end, and a spaceship requires a push at the front and a pull at the back.

Oscillators

Instead of finding oscillators with blockers on each end, we first find (infinitely long) oscillators with natural "blockers", i.e. cells that are always off. Let p be the period we are seeking. We first state an important lemma:

Lemma. 2p consecutive cells in one phase of the oscillator uniquely determines the rest. The proof is straightforward: let the cells 0 to 2p-1 be specified. If after p generations, cell p is different from the original, let cell 2p be on and otherwise let it be off. Inductively continue until all cells of the oscillator are determined. QED.

Together with the fact that XORing two oscillators gives a new oscillator, we see that all oscillators form a linear space on F_2 of dimension 2p. Let it be identified with F_2^(2p) through the isomorphism "taking the cells 0 to 2p".

There is a linear operator acting on this space, namely shifting the oscillators left by one unit. We can efficiently apply this operator k times by matrix exponentiation. Moreover, since it is bijective and acts on a finite set, it has finite order, and thus any infinite oscillator is periodic. Now, consider a length-2p strip of the form

A 0 A reversed 0

where A has length p-1. The symmetry guarantees the first 0 to be off for all p generations. By periodicity, this always-off 0 must occur another time, and if we consider what lies between these two 0s, we get an oscillator.

Rings

In construction...

What we described is essentially the theory of linear recurrences on F_2. There are much more efficient ways to compute periods, etc. using some ring theory.

The vector space we just described is isomorphic to F_2[x]/(f) where f is the feedback polynomial, with the operator corresponding to multiplication by x. This ring splits into a direct product of F_q[x]/(x^k) where qs are powers of 2, depending on the factorization of f.