Checkerboard dual

From LifeWiki
Jump to navigation Jump to search

The checkerboard dual of an isotropic non-totalistic cellular automaton is another such automaton such that any finite arrangement of live cells in an empty universe in the original rule will behave like finite perturbations in a checkerboard universe in the dual.

That is to say, for a finite pattern P, a rule R and its checkerboard dual C(R):

R(P) = C(P ⊕ checkerboard) ⊕ checkerboard

where ⊕ denotes the XOR operation.

Checkerboard duality is similar to strobing duality, but applies to isotropic rules; the checkerboard equivalent of an outer-totalistic rule (such as Life) is not generally outer-totalistic. The checkerboard dual of an isotropic non-totalistic rule is also isotropic non-totalistic if and only if the original rule is self-complementary.

The checkerboard dual of Day & Night is B1e2cn3acjkr4cny5einqy6ei7c/S01e2-ei3acjkr4-ejr5einqy6-cn7c8[1].

Finding the checkerboard dual of a given rule

Let the 'B/S conditions' of a rule be the set of 3-by-3 boxes of cells that, after iterating by one generation, result in a live centre cell. Clearly, a rule is determined uniquely by its B/S conditions. Black/white symmetric rules have exactly 256 B/S conditions (out of a possible 512).

The correct sister rule is obtained by XORing each B/S condition with a 5-cell X and the output with 1, or each condition with a 4-cell O and preserving the output, analogous to how the strobing dual is obtained by XORing each B/S condition with a 9-cell solid box.

Checkerboard duals of non-self-complimentary rules

The two equivalent methods produce a coinciding output for self-complimentary inputs, but two different ones for general rules. Just as the pair of strobing duals may alternate over time to emulate the original rule, the pair of checkerboard duals may alternate over space (for cells with even and odd parity in a checkerboard, respectively). For Life, this pair is B1e3ajkr5inqy7c/S1e2ei3ajkr4jr5inqy6cn7c and B01e2-cn3-inqy4-ny5-ajkr6-ei7c8/S01e23-inqy45-ajkr67c8.

References

  1. AforAmpere (August 4, 2017). Re: Day & Night (B3678/S34678) (discussion thread) at the ConwayLife.com forums

External links