Difference between revisions of "Replicator"

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


==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]], both the [[pre-pulsar]] and its skewed variant produce additional copies of themselves after 15 generations. However, the two copies interact, preventing any further copying. Because neither pattern copies itself in unlimited fashion, they are typically not considered true replicators.
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 be used to create [[spaceship]]s by using objects to delete one replicated part, which can be seen in HighLife's [[bomber]] and the [[pre-pulsar spaceship]] in normal Life.
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]].
 
While the vast majority of one-dimensional replicators follow Rule 90, ones bound by other rules are known, such as [[Rule 150]]<ref>http://www.conwaylife.com/forums/viewtopic.php?f=11&t=2238&p=51593#p51593</ref><ref>http://www.conwaylife.com/forums/viewtopic.php?f=11&t=3453#p61459</ref> and [http://www.wolframalpha.com/input/?i=rule+1208925819614629174771760,+range+3 Rule 1208925819614629174771760]<ref>http://www.conwaylife.com/forums/viewtopic.php?f=11&t=3453#p61463</ref>.
 
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==


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.<ref>{{Citation|last=Gardner|first=Martin|year=1983|title=Wheels, Life, and Other Mathematical Amusements|pages=226-227}}</ref> In particular, the cellular automaton supports both [[universal computer|universal computation]] (by simulating a Turing machine) and [[universal constructor|universal construction]] and so a universal computer, connected to a universal constructor, would self-replicate when given a blueprint of itself.
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.<ref>{{Citation|last=Gardner|first=Martin|year=1983|publisher=W.H. Freeman|title=Wheels, Life, and Other Mathematical Amusements|pages=226-227}}</ref> In particular, the cellular automaton supports both [[universal computer|universal computation]] (by simulating a Turing machine) and [[universal constructor|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.<ref>{{Citation|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John H.|last3=Guy|first3=Richard K.|year=2004|volume=4|edition=2nd|title=Winning Ways for Your Mathematical Plays|pages=927-961}}</ref>
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.<ref>{{Citation|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John H.|last3=Guy|first3=Richard K.|year=2004|volume=4|edition=2nd|title=Winning Ways for Your Mathematical Plays|pages=927-961}}</ref>
Line 29: Line 32:
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==
* [[Gemini]]
* [[Gemini]]
* [[Linear propagator]]
* [[Linear propagator]]


==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==
{{LinkWikipedia|Replicator_(cellular_automaton)}}
{{LinkWeisstein|Replicator.html}}
{{LinkWeisstein|Replicator.html}}
{{LinkLexicon|lex_r.htm#replicator}}
{{LinkLexicon|lex_r.htm#replicator}}

Revision as of 12:43, 21 October 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.

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

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.[5] 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.[6]

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

A universal computer and constructor is likely to exist also for B35/S236, but no specific examples have been constructed.[8] 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:[9]

  • 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. http://www.conwaylife.com/forums/viewtopic.php?f=11&t=2238&p=51593#p51593
  3. http://www.conwaylife.com/forums/viewtopic.php?f=11&t=3453#p61459
  4. http://www.conwaylife.com/forums/viewtopic.php?f=11&t=3453#p61463
  5. Gardner, Martin (1983), Wheels, Life, and Other Mathematical Amusements, W.H. Freeman, pp. 226-227
  6. Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2004), Winning Ways for Your Mathematical Plays, 4 (2nd ed.), pp. 927-961
  7. Dave Greene (November 23, 2013). "Re: Geminoid Challenge". Retrieved on November 24, 2013.
  8. David Eppstein. "B35/S236". Retrieved on February 9, 2016.
  9. Cite error: Invalid <ref> tag; no text was provided for refs named thread2648

External links

Template:LinkWeisstein