Self-complementary
An (outer-totalistic) rule is said to be self-complementary if it remains unchanged under black/white reversal, i.e. if a pattern composed of live cells in a dead universe behaves the same as an equivalent pattern composed of dead cells in a live universe.
A self-complementary rule's birth conditions completely determine its survival conditions, and vice versa, but no other constraints exist; as such there are 29 = 512 distinct self-complementary outer-totalistic rules.
Every self-complementary rule contains precisely one of B0 and S8. In the former case, the rule is strobing; in the latter case, there exists an equivalent strobing rule. Non-strobing and strobing versions of the same self-complementary rule behave identically, except that in the strobing version, patterns are inverted in every other generation, so of the 512 distinct self-complementary outer-totalistic rules, only 256 exhibit fundamentally different behavior.
Examples
The most well-known and well-investigated self-complementary rule is Day & Night (B3678/S34678); its equivalent strobing version is B01245/S0125.
Generalizations
Self-complementary rules exhibiting complex behavior, spaceships, still lifes, oscillators.replicators, rake and guns are known in to exist in higher range HROT rules. Somewhat similar behavior has been also discovered in isotropic non-totalistic self-complementary 1D cellular automata with higher ranges and custom neighborhoods[1].
It is also possible to define generalizations of self-complementary rules with more than 2 cyclical states, e.g. a 3-state rule in which every pattern behaves exactly the same, if every cell of state 1 is changed to state 2, state 2 to state 3 and state 3 back to state 1. Yoel Matveyev's Multistate cyclic rules are also a generalization of self-complementarity, where every pattern behaves exactly the same, if all live cells of a certain state are cyclically changed to the next live state[2]. Classic self-complementary rules can be emulated by multistate cyclic rules. For example, Matveyev's rule Triple-DN has 2 live states, which act exactly like Day and Night by themselves, as well as when a pattern in one live state evolves on the background of the other live state.
References
- ↑ Yoel (July 28, 2021). Re: Larger than Life (discussion thread) at the ConwayLife.com forums
- ↑ Yoel (July 24, 2020). Re: Larger than Life (discussion thread) at the ConwayLife.com forums