Difference between revisions of "Replicator"

From LifeWiki
Jump to navigation Jump to search
m (sp)
(12 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Glossary}}
:''For the cellular automaton of the same name, see [[Replicator (CA)]].''
A '''replicator''' is any pattern that produces an arbitrary number of copies of itself. There is currently no precise definition.
A '''replicator''' is any pattern that produces an arbitrary number of copies of itself. There is currently no precise definition.
__TOC__


==Natural replicators==
==Natural replicators==


 
Replicators occur naturally in some [[cellular automata]].<ref>{{cite web|url=https://www.ics.uci.edu/~eppstein/ca/replicators/ |title=Cellular Automata: Replicators |author=David Eppstein |accessdate=February 17, 2016}}</ref> 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).
Replicators occur naturally in some [[cellular automata]].<ref>{{cite web|url=https://www.ics.uci.edu/~eppstein/ca/replicators/ |title=Cellular Automata: Replicators |author=David Eppstein |accessdate=February 17, 2016}}</ref> A well-known example in a Life-like cellular automaton is the simple replicator in [[HighLife]] (B36/S23). It repeatedly copies itself along a diagonal line every 12 generations according to a one-dimensional parity rule (Wolfram Rule 90).


{| style="margin-left:auto;margin-right:auto;"
{| style="margin-left:auto;margin-right:auto;"
|[[Image:Replicator.png|frame|right|Replicator in [[HighLife]]<br />{{JavaRLE|replicator|brief}}]]
|[[Image:Replicator.png|frame|left|Replicator in HighLife<br />{{JavaRLE|replicator|brief}}.]]
|[[Image:replicator_gen12.png|framed|right|HighLife replicator after 12 generations.]]
|[[Image:Replicator_animation.gif|framed|left|HighLife replicator animation.]]
|}
|}


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. Therefore, the pre-pulsar is 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.
Other rules with replicators include [[tHighLife]].


[[Image:Prepulsar.png|frame|right|Pre-pulsar in [[Life]]<br />{{JavaRLE|prepulsar|brief}}]]
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 (CA)|Replicator]] rule (B1357/S1357) and [[Fredkin]] rule (B1357/S02468), every pattern is a replicator.
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 (CA)|Replicator]] rule (B1357/S1357) and [[Fredkin]] rule (B1357/S02468), every pattern is a replicator.


Replicators can alternatively be used to create [[shuttle]]s and [[spaceship]]s by using objects to delete one replicated part, such as HighLife's [[bomber]] and the [[pre-pulsar spaceship]] in normal Life, as well as [[Pre-pulsar shuttle 28]] and [[Pre-pulsar shuttle 29]].
Replicators can alternatively be used to create [[spaceship]]s by using objects to delete one replicated part, such as HighLife's [[bomber]] and the [[pre-pulsar spaceship]] in normal Life. [[Shuttle]]s can also be created by subduing replicators, as seen in [[Pre-pulsar shuttle 28]] and [[Pre-pulsar shuttle 29]].
 
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==
==Construction-based replicators==
Line 29: Line 30:
Prior to 2013, no explicit examples of construction-based replicators in Life were known. However, on November 23, 2013, [[Dave Greene]] constructed [[linear propagator|an explicit example]] by feeding a universal [[salvo|slow-salvo]] constructor (without any underlying universal computer) a tape of gliders that functions as a recipe for the constructor's own construction.<ref>{{Cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=1006&p=9901#p9901|title=Re: Geminoid Challenge|author=Dave Greene|date=November 23, 2013|accessdate=November 24, 2013}}</ref>
Prior to 2013, no explicit examples of construction-based replicators in Life were known. However, on November 23, 2013, [[Dave Greene]] constructed [[linear propagator|an explicit example]] by feeding a universal [[salvo|slow-salvo]] constructor (without any underlying universal computer) a tape of gliders that functions as a recipe for the constructor's own construction.<ref>{{Cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=1006&p=9901#p9901|title=Re: Geminoid Challenge|author=Dave Greene|date=November 23, 2013|accessdate=November 24, 2013}}</ref>


A universal computer and constructor is known to exist also for [[B35/S236]].<ref>{{Cite web|url=http://www.ics.uci.edu/~eppstein/ca/b35s236/|title=B35/S236|author=David Eppstein|accessdate=February 9, 2016}}</ref> Therefore, replicators exist in that rule.
A universal computer and constructor is likely to exist also for [[B35/S236]], but no specific examples have been constructed.<ref>{{Cite web|url=http://www.ics.uci.edu/~eppstein/ca/b35s236/|title=B35/S236|author=David Eppstein|accessdate=February 9, 2016}}</ref> Therefore, replicators presumably exist in that rule, as in many other rules that appear to meet the requirements for construction universality.
 
==Classifying replicators==
A classification scheme for two-dimensional replicators was proposed by [[Luka Okanishi]] in December 2016:<ref name="thread2648" />
 
* Successful replicators:
** Class S (strict); the replicated patterns appears 1, 2, 4, 4, 4, 8, 16, 8, 4, 8, ... times ({{OEIS|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 ({{OEIS|A102376}}).
** Class X (fourfold XOR): 1, 4, 8, 16, 16, 32, 32, 64, 32, 64, ... times ({{OEIS|A189007}}).
** Class U (unusual): all others.
* Failed replicators:
** Class A (almost)
** Class D (dirty)
** Class F (spacefilling)


==See Also==
==See Also==
Line 36: Line 51:


==References==
==References==
<references/>
<references>
<ref name="thread2648">{{LinkForumThread
|f      = 11
|t      = 2648
|title  = 2D Replicator Classes
|author = [[Luka Okanishi]] (AbhpzTa)
|format = ref
}}
</references>


==External Links==
==External Links==
{{LinkWeisstein|Replicator.html}}
{{LinkWeisstein|Replicator.html}}
{{LinkLexicon|lex_r.htm#replicator}}
{{LinkLexicon|lex_r.htm#replicator}}

Revision as of 20:02, 18 March 2018

For the cellular automaton of the same name, see Replicator (CA).

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

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.[2] 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.[3]

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.[4]

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

Classifying replicators

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

  • Successful replicators:
    • Class S (strict); the replicated patterns appears 1, 2, 4, 4, 4, 8, 16, 8, 4, 8, ... times (OEISicon light 11px.pngA173531).
    • 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 (OEISicon light 11px.pngA102376).
    • Class X (fourfold XOR): 1, 4, 8, 16, 16, 32, 32, 64, 32, 64, ... times (OEISicon light 11px.pngA189007).
    • Class U (unusual): all others.
  • Failed replicators:
    • Class A (almost)
    • Class D (dirty)
    • Class F (spacefilling)

See Also

References

  1. David Eppstein. "Cellular Automata: Replicators". Retrieved on February 17, 2016.
  2. Gardner, Martin (1983), Wheels, Life, and Other Mathematical Amusements, W.H. Freeman, pp. 226-227
  3. Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2004), Winning Ways for Your Mathematical Plays, 4 (2nd ed.), pp. 927-961
  4. Dave Greene (November 23, 2013). "Re: Geminoid Challenge". Retrieved on November 24, 2013.
  5. David Eppstein. "B35/S236". Retrieved on February 9, 2016.
  6. Cite error: Invalid <ref> tag; no text was provided for refs named thread2648

External Links

Template:LinkWeisstein