OCA:Replicator
| Replicator | |
| View static image | |
| Rulestring | 1357/1357 B1357/S1357 |
|---|---|
| Rule integer | 87210 |
| Character | Explosive |
| Black/white reversal | B02468/S02468 |
- For other uses of 'Replicator', see Replicator (disambiguation).
Replicator is a Life-like cellular automaton where a cell survives or is born if there are an odd number of neighbors. It is one of two Life-like Fredkin replicator rules. Under this ruleset, every pattern self-replicates; furthermore, every pattern will eventually produce an arbitrary number of copies of itself, all arbitrarily far away from each other.
Replication property
The replication property follows from a property of Fredkin replicator rules, in which patterns can be modelled as an infinite grid whose entries are elements of the cyclic group Zn, where n is the number of states. In this case, n=2, 0 is the off state, and 1 is the on state. The rule can be expressed equivalently as assigning a new value to a cell by summing all neighboring cells. Since Zn is an abelian group, addition is commutative and associative; hence applying the rule to a sum (XOR) of two patterns is the same as summing the two patterns after the rule is applied to each one.
Thus, to find the nth generation of a pattern, it suffices to XOR together the nth generation of each of the single cells which compose the pattern. A single cell is a replicator. More specifically, an on-cell at (0,0) at time 0 will produce, at time 2n, 8 on-cells at all positions (b,c) where b and c are any of -2n, 0, or 2n, and b and c are not both 0 (this can be proven using induction on n). When n is large enough, the 8 cells are arbitrarily far away, and thus, for a pattern, the XOR sum of the (2n)th generation of each of its cells forms the pattern's (2n)th generation, 8 copies of the original. Repeating this process produces an arbitrary number of copies, all at arbitrary distance.
The replication habit seen can be classified as (150,90), where the classification (E,C) refers to the one-dimensional rules simulated by the edge of the replicator and the diagonal of the square.[1]
It is not a self-complementary rule, so its strobing and checkerboard duals are alternating pairs in time and space, respectively. However, they satisfy certain properties.
- It is one of 29=512 outer-totalistic rules whose strobing duals are themselves alternating with their black/white reversal, meaning that its output is invariant under action of XORing its input with an infinite all-on state. (This condition is equivalent to each survival condition being the opposite of the birth condition with 9 minus its neighbour count, so only the 9 birth conditions provide degrees of freedom.)
- It is one of 24=16 outer-totalistic rules whose checkerboard duals have this property, making it invariant under XOR with an infinite checkerboard. (The full set is given by the rules whose birth and survival conditions are a member of {the empty set, 1357, 02468, and 012345678}.)
It is one of 4 rules with both of these properties at once, the others being its dual, B/S and B012345678/S012345678.
Replicator's output is also invariant under XORing of its input with the lattice formed by a checkerboard of 2 × 2 squares, due to the property that each cell has an even number of on neighbours.
The number of cells on the nth iteration from a single cell is given by OEIS sequence A160239(n).
Replicator 2
| Fredkin | |
| Rulestring | 02468/1357 B1357/S02468 |
|---|---|
| Rule integer | 174762 |
| Character | Explosive |
| Black/white reversal | B1357/S02468 |
| Strobing dual | B02468/S1357 |
| Checkerboard dual | B1357/S02468 |
Replicator 2, also known as Fredkin, is a related totalistic replicator rule, where a cell survives or is born if the number of neighbors, including itself, is odd. It has the totalistic rulestring 13579. Like Replicator, every pattern self-replicates, although according to (150,150) instead.[1]
Of the outer-totalistic rules that are self-complementary (and have a single checkerboard dual), it is one of 4 rules that are their own checkerboard dual (the others being B02468/S1357 (its strobing dual), B/S012345678 and B012345678/S).
The number of cells on the nth iteration from a single cell is given by A246035(n). It can be seen as the Cartesian product of Wolfram rule 150 with itself, so is equivalently A071053(n)2.
Other replicators
Analogous behaviours to Replicator and Fredkin occur in the von Neumann neighbourhood rules B13/S13 and B13/S024, respectively, encodable as the isotropic non-totalistic rules B1e2ak3einqy4jnry5einqy6ak7e/S1e2ak3einqy4jnry5einqy6ak7e and B1e2ak3einqy4jnry5einqy6ak7e/S01c2-ak3acjkr4-jnry5acjkr6-ak7c8. Their replication habits can be described by (90,90) and (90,150), respectively, where the classification (E,C) refers to the diagonal edge and orthogonal cross-section of the diamond. The former's population is given by A102376(n)=4n.bit_count(), the latter by A072272.
References
- ↑ 1.0 1.1 Connor Steppie (November 1, 2018). New method of classifying two-dimensional replicators (discussion thread) at the ConwayLife.com forums
External links
- Replicator (discussion thread) at the ConwayLife.com forums
- MCell built-in Life rules: Replicator at Mirek Wójtowicz's Cellebration page
- MCell built-in Vote for Life rules: Fredkin at Mirek Wójtowicz's Cellebration page