Replicator: Difference between revisions
No edit summary |
precise definition? |
||
| Line 1: | Line 1: | ||
A '''replicator''' is any pattern that produces copies of itself. There is currently no precise definition. | A '''replicator''' is any pattern that produces exact copies of itself infinitely. There is currently no precise definition. | ||
__TOC__ | __TOC__ | ||
Revision as of 08:40, 17 March 2016
A replicator is any pattern that produces exact copies of itself infinitely. 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).
 RLE: here |
 |
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 classed as a replicator, although it can be hassled to form shuttles. The skewed variant of the pre-pulsar, and other pre-pulsar like patterns of consistent spacing, also copy themselves over time, and also cannot replicate infinitely.
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.
Replicators can be used to create spaceships by using objects to delete one replicated part, which can be seen in HighLife's bomber and the pre-pulsar spaceship in normal Life.
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
- ↑ David Eppstein. "Cellular Automata: Replicators". Retrieved on February 17, 2016.
- ↑ 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.
External Links
- Replicator at the Life Lexicon