Replicator

For other uses of 'Replicator', see Replicator (disambiguation).

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

Common definitions

While there exist many conflicting definitions as to what a replicator is, most patterns classified as replicators tend to satisfy the following properties:

• Replicators are bound by a "parity" rule, in which the replicator will always revert to having a certain number of copies after a given integer multiple of a perfect power, usually 2, although some replicators based on higher powers exist. In effect, replicators must also be sawtooths. Replicators which do not revert in such a fashion are usually considered to be wickstretchers or spacefillers, or may belong to another class entirely outside of these three.
• In addition, replicators are also generally required to leave no debris, especially if any such debris would interfere with further replication. Patterns which do leave behind objects are referred to as "dirty" replicators, and many stop replicating after an amount of time due to the chaos created, with an exception of the replicator in B36/S245. Debris also prevents replicators from acting as a sawtooth.

There are further ways in which a replicator can be defined, such as strength, which measures its power to be a unit cell.

Common classifications

One common way to classify different types of replicators is "dimensionality". This gives two main classes of replicator:

• one-dimensional replicators, which replicate along a line and behave as linear sawtooths,
• two-dimensional replicators, which replicate across the plane and behave as quadratic sawtooths.

These two cases are the most-commonly seen on the standard 2D square tiling; different tilings can allow for different replicator dimensionality classifications, as can different neighbourhoods. Even the square tiling harbors replicators which diverge from this classification, such as a three-way replicator which traces out a Sierpinski triangle shape rather than a line or square; these could be considered log2(3)-dimensional. Such replicators have also been sighted on the hexagonal tiling.

Examples in Life

Elementary replicators

As of October 2024, no finite elementary replicators are known in Life, however there are patterns which can be considered "failed" replicators which are incapable of expanding infinitely:

• The pre-pulsar produces two exact copies 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.
• The pi-heptomino sequence produces two pi-heptominos to each side after 26 generations, however these are rapidly attacked by the rest of the explosion and are therefore denied further evolution.

Construction-based replicators

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).

Examples in other rules

Replicators occur naturally in some cellular automata. Possibly the most well-known example in a Life-like cellular automaton is the 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.

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).

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.

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
• Rules with interesting replicators (discussion thread) at the ConwayLife.com forums
• Rules With Oblique Replicators (discussion thread) at the ConwayLife.com forums
• Rules With Quadratic (2D) Replicators (discussion thread) at the ConwayLife.com forums