Difference between revisions of "Replicator"

From LifeWiki
Jump to navigation Jump to search
(update with more information)
Line 1: Line 1:
[[Image:Replicator.png|frame|right|Replicator in [[HighLife]]<br />{{JavaRLE|replicator|brief}}]]
A '''replicator''' is any pattern that produces copies of itself. There is currently no precise definition.
{{Glossary}}
A '''replicator''' is any pattern that produces copies of itself.


Replicators occur naturally in some [[cellular automata]]. The best-known example is the replicator in [[HighLife]] (B36/S23), which evolves into four half-[[traffic light]]s in regular Life. In the [[Replicator (CA)|Replicator]] rule (B1357/S1357) and [[Replicator 2]] rule (B1357/S02468), every pattern is a replicator. A single alive [[cell]] is a replicator in many B1 rules, including [[Gnarl]] (B1/S1).
__TOC__


There exists a replicator in any cellular automaton with a [[universal constructor]]. Therefore it had been known, that Life, which has a universal constructor, had replicators, before [[Dave Greene]] found [[linear propagator|an explicit example]] on November 23, 2013.<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>
==Natural replicators==


A universal 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>
 
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;"
|[[Image:Replicator.png|frame|right|Replicator in [[HighLife]]<br />{{JavaRLE|replicator|brief}}]]
|[[Image:replicator_gen12.png|framed|right|HighLife replicator after 12 generations.]]
|}
 
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.
 
[[Image:Prepulsar.png|frame|right|Pre-pulsar in [[Life]]<br />{{JavaRLE|prepulsar|brief}}]]
 
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.
 
==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.
 
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=Second Edition|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 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.


==See Also==
==See Also==

Revision as of 07:31, 18 February 2016

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

Natural replicators

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

Replicator in HighLife
RLE: here
HighLife replicator after 12 generations.

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.

Pre-pulsar in Life
RLE: here

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.

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 known to exist also for B35/S236.[5] Therefore, replicators exist in that rule.

See Also

References

  1. ↑ David Eppstein. "Cellular Automata: Replicators". Retrieved on February 17, 2016.
  2. ↑ Gardner, Martin (1983), Wheels, Life, and Other Mathematical Amusements, pp. 226-227
  3. ↑ Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2004), Winning Ways for Your Mathematical Plays, 4 (Second Edition 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.

External Links

Template:LinkWeisstein

Retrieved from "https://conwaylife.com/w/index.php?title=Replicator&oldid=21886"