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.