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

Replicator in HighLife
RLE: here .
HighLife replicator animation.

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

gollark: No.
gollark: (`dofile` does return things, yes, so it should work)
gollark: I gues you could use `dofile`, but it may be slightly eeeevil to do so.
gollark: What would you suggest, O Squid of Dev(ing)?
gollark: Try `./.folder/file.lua`?

See also

References
  1. David Eppstein. "Cellular Automata: Replicators". Retrieved on February 17, 2016.
  2. muzik (October 4, 2017). Re: Thread for basic non-CGOL questions (discussion thread) at the ConwayLife.com forums
  3. muzik (June 29, 2018). Replicators and other patterns that simulate even 1D rules (discussion thread) at the ConwayLife.com forums
  4. AforAmpere (June 29, 2018). Re: Replicators that simulate even 1D rules (discussion thread) at the ConwayLife.com forums
  5. LaundryPizza03 (December 25, 2017). Re: 2D Replicator Classes (discussion thread) at the ConwayLife.com forums
  6. AlephAlpha (March 24, 2019). Re: 2D Replicator Classes (discussion thread) at the ConwayLife.com forums
  7. Gardner, Martin (1983), Wheels, Life, and Other Mathematical Amusements, W.H. Freeman, pp. 226-227
  8. Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2004), Winning Ways for Your Mathematical Plays, 4 (2nd ed.), pp. 927-961
  9. Dave Greene (November 23, 2013). "Re: Geminoid Challenge". Retrieved on November 24, 2013.
  10. David Eppstein. "B35/S236". Retrieved on February 9, 2016.
  11. Luka Okanishi (AbhpzTa) (December 23, 2016). 2D Replicator Classes (discussion thread) at the ConwayLife.com forums
  12. muzik (November 1, 2018). New method of classifying two-dimensional replicators (discussion thread) at the ConwayLife.com forums
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.