Self-complementary: Difference between revisions
No edit summary |
→External links: https://conwaylife.com/forums/viewtopic.php?p=170335#p170335 |
||
| (12 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
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 [[cell]]s 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 {{eq|2{{sup|9}}|512}} distinct self-complementary [[Life-like cellular automaton|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 [[black/white reversal|inverted]] in every other generation, so of the 512 distinct self-complementary outer-totalistic rules, only 256 exhibit fundamentally different behavior. | 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 [[black/white reversal|inverted]] in every other generation, so of the 512 distinct self-complementary outer-totalistic rules, only 256 exhibit fundamentally different behavior. | ||
| Line 8: | Line 8: | ||
==Examples== | ==Examples== | ||
<!-- {{Main|List of self-complementary rules}} ---> | <!-- {{Main|List of self-complementary rules}} ---> | ||
The most well-known and well-investigated self-complementary rule is | The most well-known and well-investigated self-complementary rule is {{rl|Day & Night}} (B3678/S34678); its equivalent strobing version is B01245/S0125. | ||
==Generalizations== | ==Generalizations== | ||
Self-complementary rules exhibiting complex behavior, [[spaceship | Self-complementary rules exhibiting complex behavior are known to exist in [[higher-range outer-totalistic]] rules, where [[spaceship]]s, [[still life]]s, [[oscillator]]s, [[replicator]]s, [[rake]]s and [[gun]]s inhabit.<ref name="post138010" /> Somewhat similar behavior has been also discovered in isotropic non-totalistic self-complementary [[1D cellular automata]] with higher ranges and custom neighborhoods.<ref name="post134179" /> | ||
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 | 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 rule|multistate]] [[cyclic rule|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.<ref name="post101012" /> Classic self-complementary rules can be emulated by multistate cyclic rules. For example, Matveyev's rule [[Rule:Triple-DN|Triple-DN]] has 2 live states, which act exactly like {{rl|Day & Night}} by themselves, as well as when a pattern in one live state evolves on the background of the other live state. | ||
==References== | ==References== | ||
| Line 22: | Line 22: | ||
|title = Re: Larger than Life | |title = Re: Larger than Life | ||
|p = 134179 | |p = 134179 | ||
|author = Yoel | |author = Yoel Matveyev | ||
|date = July 28, 2021 | |date = July 28, 2021 | ||
}}</ref> | }}</ref> | ||
<ref name="post101012">{{LinkForumThread | <ref name="post101012">{{LinkForumThread | ||
|format = ref | |format = ref | ||
|title = Re: | |title = Re: Gluonic | ||
|p = 101012 | |p = 101012 | ||
|author = Yoel | |author = Yoel Matveyev | ||
|date = July 24, 2020 | |date = July 24, 2020 | ||
}}</ref> | |||
<ref name="post138010">{{LinkForumThread | |||
|format = ref | |||
|title = Re: Larger than Life | |||
|p = 138010 | |||
|author = Yoel Matveyev | |||
|date = November 23, 2021 | |||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
== External links == | ==External links== | ||
{{ | * {{LinkForumThread|format=ref|f=11|t=3493|title=Day and Knight rule group}} | ||
* {{LinkForumThread|format=ref|f=11|t=6125|title=Hexagonal self-complementary rules}} | |||
* {{LinkForumThread|format=ref|f=11|t=6208|title=The other five interesting self-complementary outer-totalistic rules}} | |||
[[Category:Self-complementary rules| ]] | |||
__NOTOC__ | |||
Latest revision as of 18:41, 2 November 2023
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 29 = 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.[1] Somewhat similar behavior has been also discovered in isotropic non-totalistic self-complementary 1D cellular automata with higher ranges and custom neighborhoods.[2]
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.[3] 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.
References
- ↑ Yoel Matveyev (November 23, 2021). Re: Larger than Life (discussion thread) at the ConwayLife.com forums
- ↑ Yoel Matveyev (July 28, 2021). Re: Larger than Life (discussion thread) at the ConwayLife.com forums
- ↑ Yoel Matveyev (July 24, 2020). Re: Gluonic (discussion thread) at the ConwayLife.com forums
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