OCA:Replicator: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
==Replication Property== | ==Replication Property== | ||
The replication property follows from a property of Fredkin replicator rules, which can be modelled as elements of the [http://en.wikipedia.org/wiki/Cyclic_group cyclic group] Z/nZ, where n is the number of states | 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 [http://en.wikipedia.org/wiki/Cyclic_group cyclic group] Z/nZ, 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 Z/nZ 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 2^n, 8 on-cells at all positions (b,c) where b and c are any of -2^n, 0, or 2^n, 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 (2^n)th generation of each of its cells forms the pattern's (2^n)th generation, 8 copies of the original. Repeating this process produces an arbitrary number of copies, all at arbitrary distance. | 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 2^n, 8 on-cells at all positions (b,c) where b and c are any of -2^n, 0, or 2^n, 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 (2^n)th generation of each of its cells forms the pattern's (2^n)th generation, 8 copies of the original. Repeating this process produces an arbitrary number of copies, all at arbitrary distance. | ||
Revision as of 05:19, 17 February 2010
| Replicator | |
| Rulestring | 1357/1357 B1357/S1357 |
|---|---|
| Character | Explosive |
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 Z/nZ, 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 Z/nZ 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 2^n, 8 on-cells at all positions (b,c) where b and c are any of -2^n, 0, or 2^n, 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 (2^n)th generation of each of its cells forms the pattern's (2^n)th generation, 8 copies of the original. Repeating this process produces an arbitrary number of copies, all at arbitrary distance.