Cellular Automata: Replicators

A replicator is usually defined as a cellular automaton pattern which can make copies of itself. This definition is somewhat vague, but there are so few examples known that it would be unhelpful to try to be more precise. Replicators are interesting not only in themselves, but because they can be used to build many other types of patterns: high-period oscillators, glider guns, puffers and spaceships, and pseudo-random number generators.

Most replicators work accoding to a parity rule: there is a (usually one-dimensional) grid of possible replicator positions, such that, if replicators are placed at certain grid positions, they produce new replicators at the positions with an odd number of replicators in neighboring cells. If the grid positions are spaced k units apart, and the period (number of generations between each replication) is p, then the resulting pattern of oscillators expands at a speed of kc/p, with a sawtooth growth rate in which the number of active cells repeatedly increases to linear (or quadratic, for two dimensional grids) then decreases to a constant. The minima of the number of active cells occur at generations that are powers of two times the period.

Parity-rule replicators are fairly common in rules with B1 (birth on a single neighbor, in standard semitotalistic notation), but those rules are not very interesting because any pattern quickly grows to infinity in all directions, so gliders, oscillators, and similar structures are impossible. The more interesting rules are those with B0, B2 or B3, in which gliders are possible (and many gliders are known).

Among these rules, only the following replicators are known:

It is believed that B3/S23 (Conway's Life) and B35/S236 also support replicators due to construction universality, but explicit replicators for those rules have not been constructed.