Difference between revisions of "Replicator"
(31 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
A '''replicator''' is any pattern that produces copies of itself. | :''For the cellular automaton of the same name, see [[OCA:Replicator]].'' | ||
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]].<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]]). | |||
{| style="margin-left:auto;margin-right:auto;" | |||
|[[Image:Replicator.png|frame|left|Replicator in HighLife<br />{{JavaRLE|replicator|brief}}.]] | |||
|[[Image:Replicator_animation.gif|framed|left|HighLife replicator animation.]] | |||
|} | |||
==See | 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)|Replicator]] rule (B1357/S1357) and [[Fredkin]] rule (B1357/S02468), every pattern is a replicator. | |||
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 name="post51593" /><ref name="post61459" /> and [http://www.wolframalpha.com/input/?i=rule+1208925819614629174771760,+range+3 Rule 1208925819614629174771760]<ref name="post61463" />. | |||
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.<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> | |||
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> 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.<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== | |||
===Okanishi's classifications=== | |||
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) | |||
===XOR-based classifications=== | |||
An alternative classification for replicators was proposed in November 2018, based on underlying XOR rules.<ref name="post65242" /> | |||
==See also== | |||
* [[Gemini]] | * [[Gemini]] | ||
* [[Linear propagator]] | * [[Linear propagator]] | ||
==References== | ==References== | ||
<references/> | <references> | ||
<ref name="post51593">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Thread for basic non-CGOL questions | |||
|p = 51593 | |||
|author = muzik | |||
|date = October 4, 2017 | |||
}}</ref> | |||
<ref name="post61459">{{LinkForumThread | |||
|format = ref | |||
|title = Replicators and other patterns that simulate even 1D rules | |||
|p = 61459 | |||
|author = muzik | |||
|date = June 29, 2018 | |||
}}</ref> | |||
<ref name="post61463">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Replicators that simulate even 1D rules | |||
|p = 61463 | |||
|author = AforAmpere | |||
|date = June 29, 2018 | |||
}}</ref> | |||
<ref name="thread2648">{{LinkForumThread | |||
|f = 11 | |||
|t = 2648 | |||
|title = 2D Replicator Classes | |||
|author = [[Luka Okanishi]] (AbhpzTa) | |||
|format = ref | |||
}}</ref> | |||
<ref name="post65242">{{LinkForumThread | |||
|format = ref | |||
|title = New method of classifying two-dimensional replicators | |||
|p = 65242 | |||
|author = muzik | |||
|date = November 1, 2018 | |||
}}</ref> | |||
</references> | |||
==External | ==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 17:38, 5 April 2019
- For the cellular automaton of the same name, see OCA:Replicator.
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).
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] 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.[8] 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:[9]
- 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.[10]
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
- ↑ 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). 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
External links
- Replicator at Wikipedia
- Replicator at the Life Lexicon