# Replicator

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

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

## Natural replicators

Replicators occur naturally in some cellular automata.[1] 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 (Wolfram Rule 90).

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[2][3] and Rule 1208925819614629174771760.[4] 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[5] and hexagonal-grid[6] 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.[7] 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.[8]

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.[9] 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.[10] 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:[11]

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

- Class S (strict); the replicated patterns appears 1, 2, 4, 4, 4, 8, 16, 8, 4, 8, ... times (
- 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.[12]

## See also

## References

- David Eppstein. "Cellular Automata: Replicators". Retrieved on February 17, 2016.
- muzik (October 4, 2017). Re: Thread for basic non-CGOL questions (discussion thread) at the ConwayLife.com forums
- muzik (June 29, 2018). Replicators and other patterns that simulate even 1D rules (discussion thread) at the ConwayLife.com forums
- AforAmpere (June 29, 2018). Re: Replicators that simulate even 1D rules (discussion thread) at the ConwayLife.com forums
- LaundryPizza03 (December 25, 2017). Re: 2D Replicator Classes (discussion thread) at the ConwayLife.com forums
- AlephAlpha (March 24, 2019). Re: 2D Replicator Classes (discussion thread) at the ConwayLife.com forums
- Gardner, Martin (1983),
*Wheels, Life, and Other Mathematical Amusements*, W.H. Freeman, pp. 226-227 - Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2004),
*Winning Ways for Your Mathematical Plays*,**4**(2nd ed.), pp. 927-961 - Dave Greene (November 23, 2013). "Re: Geminoid Challenge". Retrieved on November 24, 2013.
- David Eppstein. "B35/S236". Retrieved on February 9, 2016.
- Luka Okanishi (AbhpzTa) (December 23, 2016). 2D Replicator Classes (discussion thread) at the ConwayLife.com forums
- muzik (November 1, 2018). New method of classifying two-dimensional replicators (discussion thread) at the ConwayLife.com forums