Self-complementary

A two-state cellular automaton 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.

For a self-complementary rule, the birth conditions completely determine the survival conditions, and vice versa, but no other constraints exist; as such there are 2⁹ = 512 distinct self-complementary Life-like 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 are known to exist in higher-range outer-totalistic rules, where spaceships, still lifes, oscillators, replicators, rakes and guns inhabit. Somewhat similar behavior has been also discovered in isotropic non-totalistic self-complementary 1D cellular automata with higher ranges and custom neighborhoods.

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 another live state. 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 & Night by themselves, as well as when a pattern in one live state evolves on the background of the other live state.

External links

• Day and Knight rule group (discussion thread) at the ConwayLife.com forums
• Hexagonal self-complementary rules (discussion thread) at the ConwayLife.com forums
• The other five interesting self-complementary outer-totalistic rules (discussion thread) at the ConwayLife.com forums