Replicator

For the cellular automaton of the same name, see OCA:Replicator.

A replicator is any pattern that produces an arbitrary number of copies of itself. There is currently no precise definition.

Natural replicators

Replicators occur naturally in some cellular automata. Possibly the most well-known example in a Life-like cellular automaton is the simple replicator in HighLife (B36/S23), which repeatedly copies itself along a diagonal line every 12 generations according to a one-dimensional parity rule (commonly cited as Wolfram Rule 90, however a closer analysis puts Rule 6, range 1/2 as a more appropiate classification).

Replicator in HighLife RLE: here

Replication sequence

Other rules with replicators include tHighLife.

In Life, the pre-pulsar produces an exact copy of itself after 15 generations. However, these duplicated copies then react with each other to form the pulsar, instead of replicating again. The pre-pulsar is therefore generally not considered a true replicator. The skewed variant of the pre-pulsar, and other pre-pulsar-like patterns of consistent spacing, also copy themselves after 15 generations, and also cannot replicate infinitely.

Parity-rule replicators are common in B1 rules. For example, the pattern consisting of a single alive cell is a replicator in many B1 rules such as Gnarl (B1/S1). In the parity-rule Life-like cellular automata Replicator rule (B1357/S1357) and Fredkin rule (B1357/S02468), every pattern is a replicator.

Replicators can alternatively be used to create spaceships by using objects to delete one replicated part, such as HighLife's bomber and the pre-pulsar spaceship in normal Life. Shuttles can also be created by subduing replicators, as seen in Pre-pulsar shuttle 28 and Pre-pulsar shuttle 29.

While the vast majority of one-dimensional replicators follow Rule 90, ones bound by other rules are known, such as Rule 150 and Rule 1208925819614629174771760. However, the last is not a sawtooth.

Two-dimensional replicators will either be a square (if the fastest travelling corner of the mass of replicators is moving either orthogonally or diagonally), a rectangle (if some of the replicators are moving in an oblique direction), or a rhombus (if some of the replicators are moving faster than the others in a certain direction).

Natural three-way replicators (which may be considered log2(3)-dimensional replicators) have been noted in both square and hexagonal-grid rules.

Construction-based replicators

John von Neumann proved the existence of a pattern of about 200,000 cells that self-replicates in a 29-state von Neumann neighbourhood cellular automaton. In particular, the cellular automaton supports both universal computation (by simulating a Turing machine) and universal construction and so a universal computer, connected to a universal constructor, would self-replicate when given a blueprint of itself.

In 1982, Berlekamp, Conway, and Guy proved that Life supports universal computation and universal construction, and thus that there exist self-replicating machines in Life.

Prior to 2013, no explicit examples of construction-based replicators in Life were known. However, on November 23, 2013, Dave Greene constructed an explicit example by feeding a universal slow-salvo constructor (without any underlying universal computer) a tape of gliders that functions as a recipe for the constructor's own construction. In 2018, the emergence of the 0E0P metacell enabled the construction of B3/S23 replicators of every class in Okanishi's classification (explained below).

A universal computer and constructor is likely to exist also for B35/S236, but no specific examples have been constructed. Therefore, replicators presumably exist in that rule, as in many other rules that appear to meet the requirements for construction universality.

Classifying replicators

Okanishi's classifications

A classification scheme for two-dimensional replicators was proposed by Luka Okanishi in December 2016:

• Successful replicators:
  • Class S (strict); the replicated patterns appears 1, 2, 4, 4, 4, 8, 16, 8, 4, 8, ... times ( A173531).
  • Class R (rectangular); same as above, although all copies of the replicator must be present.
  • Class Q (quadruple); the replicated pattern appears 1, 4, 4, 16, 4, 16, 16, 64, 4, 16, ... times ( A102376).
  • Class X (fourfold XOR): 1, 4, 8, 16, 16, 32, 32, 64, 32, 64, ... times ( A189007).
  • Class U (unusual): all others.
• Failed replicators:
  • Class A (almost)
  • Class D (dirty)
  • Class F (spacefilling)

XOR-based classifications

An alternative classification for replicators was proposed in November 2018, based on underlying XOR rules. This classification was soon abandoned with the widening support of outer-totalistic rules of higher ranges, which revealed many more replication habits which did not fit into this system.

See also

• Gemini
• Linear propagator

External links

• Replicator at Wikipedia

• Replicator at the Life Lexicon