Difference between revisions of "OCA:2×2"
m (Fixed apgcode format) |
|||
(32 intermediate revisions by 13 users not shown) | |||
Line 1: | Line 1: | ||
{{Rule|name=2×2|imgname=2x2|s=125| | {{Rule | ||
|name = 2×2 | |||
|imgname = 2x2 | |||
|char = Chaotic | |||
|b = 36 | |||
|s = 125 | |||
|ruleinteger = 19528 | |||
|reversal = B012458/S0134678 | |||
|animated = true | |||
}} | |||
'''2×2''' is a [[cellular automaton#Well-known Life-like cellular automata|Life-like cellular automaton]] in which [[cell]]s survive from one generation to the next if they have 1, 2 or 5 [[neighbours]], and are born if they have 3 or 6 neighbours. It thus has rulestring "B36/S125". Patterns under the rule have a chaotic evolution similar to those under the [[Conway's Game of Life|standard Life rules]], but the chaos tends to die out much more quickly. | '''2×2''' is a [[cellular automaton#Well-known Life-like cellular automata|Life-like cellular automaton]] in which [[cell]]s survive from one generation to the next if they have 1, 2 or 5 [[neighbours]], and are born if they have 3 or 6 neighbours. It thus has rulestring "B36/S125". Patterns under the rule have a chaotic evolution similar to those under the [[Conway's Game of Life|standard Life rules]], but the chaos tends to die out much more quickly. | ||
Line 9: | Line 18: | ||
[[Image:2x2block_evolve.png|framed|center|The 2x2 block evolution rule]] | [[Image:2x2block_evolve.png|framed|center|The 2x2 block evolution rule]] | ||
Note that, as this emulates a Margolus neighbourhood, the resulting block appears at the center of the original four blocks. Thus, patterns that are originally made up of 2×2 blocks will forever be made up of 2×2 blocks, but the block partition will be offset by one [[cell]] in the odd [[generation]]s from the even generations. By examining the image above, one can see that a Life-like cellular automaton will emulate a Margolus block cellular automaton if and only if the following four equations are satisfied: B4 = S4, B5 = S6 = S7, B3 = S5, B1 = B2 = S3, where the first equation for example means that the birth condition for cells with four neighbours must equal the survival condition for cells with four neighbours. There are 2<sup>12</sup> = 4096 such rules, which emulate 2<sup>6</sup> = 64 different block cellular automata. | Note that, as this emulates a Margolus neighbourhood, the resulting block appears at the center of the original four blocks. Thus, patterns that are originally made up of 2×2 blocks will forever be made up of 2×2 blocks, but the block partition will be offset by one [[cell]] in the odd [[generation]]s from the even generations. By examining the image above, one can see that a Life-like cellular automaton will emulate a Margolus block cellular automaton if and only if the following four equations are satisfied: B4 = S4, B5 = S6 = S7, B3 = S5, B1 = B2 = S3, where the first equation for example means that the birth condition for cells with four neighbours must equal the survival condition for cells with four neighbours. There are 2<sup>12</sup> = 4096 such rules, which emulate 2<sup>6</sup> = 64 different block cellular automata. Any arrangement of cells that fits within a 2x2 bounding box can simulate these using isotropic non-totalistic rules. | ||
This rule can be seen to satisfy the above equations because 4 is neither a birth condition nor a survival condition, 5 is not a birth condition and 6 and 7 are not survival conditions, 3 is a birth condition and 5 is a survival condition, and 3 is not a survival condition and 1 and 2 are not birth conditions. | This rule can be seen to satisfy the above equations because 4 is neither a birth condition nor a survival condition, 5 is not a birth condition and 6 and 7 are not survival conditions, 3 is a birth condition and 5 is a survival condition, and 3 is not a survival condition and 1 and 2 are not birth conditions. | ||
The [[non-totalistic Life-like cellular automaton]] B3i4int5ey6k7e/S1e2k3ey4irt5i can be used to simulate this rule. 1x1 cells simulate the clusters of 2x2 blocks, and only every second generation plays, since odd generations have the offset. | |||
==Notable patterns== | ==Notable patterns== | ||
Line 21: | Line 32: | ||
of structure, for example often having islands that stabilise each other. | of structure, for example often having islands that stabilise each other. | ||
Many still lifes from Life are also still lifes in 2×2, For example, the [[beehive]], [[tub]], [[loaf]], [[pond]] and [[mango]]. | Many still lifes from Life are also still lifes in 2×2, For example, the [[beehive]], [[tub]], [[loaf]], [[pond]] and [[mango]]. | ||
{{EmbedViewer | |||
|pname = 2x2stills | |||
|position = center | |||
|caption = Some sample still lifes. | |||
|viewerconfig = #C [[ THUMBSIZE 2 ]] | |||
}} | |||
====Enumerating still lifes==== | ====Enumerating still lifes==== | ||
Line 95: | Line 112: | ||
|- | |- | ||
! 1 | ! 1 | ||
| [[Image:2x2_stilllife_rank1.png]] | | [[Image:2x2_stilllife_rank1.png]] ([[domino]]) | ||
| 2 | | 2 | ||
| 0.582 | | 0.582 | ||
Line 130: | Line 147: | ||
|- | |- | ||
! 8 | ! 8 | ||
| [[Image:2x2_stilllife_rank8.png]] | | [[Image:2x2_stilllife_rank8.png]] ([[beehive]]) | ||
| 6 | | 6 | ||
| 0.00384 | | 0.00384 | ||
|- | |- | ||
! 9 | ! 9 | ||
| [[Image:2x2_stilllife_rank9.png]] | | [[Image:2x2_stilllife_rank9.png]] ([[tub]]) | ||
| 4 | | 4 | ||
| 0.00322 | | 0.00322 | ||
Line 158: | Line 175: | ||
|- | |- | ||
! 12 | ! 12 | ||
| [[Image:2x2_stilllife_rank12.png]] | | [[Image:2x2_stilllife_rank12.png]] ([[loaf]]) | ||
| 7 | | 7 | ||
| 5.8×10<sup>-4</sup> | | 5.8×10<sup>-4</sup> | ||
Line 178: | Line 195: | ||
|- | |- | ||
! 16 | ! 16 | ||
| [[Image:2x2_stilllife_rank16.png]] | | [[Image:2x2_stilllife_rank16.png]] ([[aircraft carrier]]) | ||
| 6 | | 6 | ||
| 2.23×10<sup>-4</sup> | | 2.23×10<sup>-4</sup> | ||
|- | |- | ||
! 17 | ! 17 | ||
| [[Image:2x2_stilllife_rank17.png]] | | [[Image:2x2_stilllife_rank17.png]] ([[pond]]) | ||
| 8 | | 8 | ||
| 1.94×10<sup>-4</sup> | | 1.94×10<sup>-4</sup> | ||
|- | |- | ||
! 18 | ! 18 | ||
| [[Image:2x2_stilllife_rank18.png]] | | [[Image:2x2_stilllife_rank18.png]] ([[mango]]) | ||
| 8 | | 8 | ||
| 1.28×10<sup>-4</sup> | | 1.28×10<sup>-4</sup> | ||
Line 210: | Line 227: | ||
Many of the [[period]] 2 oscillators in 2×2 have a single-cell 'on-off' [[rotor]], with small variations in the | Many of the [[period]] 2 oscillators in 2×2 have a single-cell 'on-off' [[rotor]], with small variations in the | ||
[[stator]] of the oscillator. These occur fairly frequently naturally. | [[stator]] of the oscillator. These occur fairly frequently naturally. | ||
{{EmbedViewer | |||
|pname = 2x2period2oscillators | |||
|position = center | |||
|caption = Some period 2 oscillators. | |||
|viewerconfig = #C [[ THUMBSIZE 2 AUTOSTART GPS 2 ]] | |||
}} | |||
====Higher-period oscillators==== | ====Higher-period oscillators==== | ||
One of the most interesting aspects of the 2×2 rule is the large number of naturally-occurring higher-period oscillators. Oscillators with periods 3, 4, 5, 6, 10, 14, 22 and 26 are all relatively frequent, and oscillators are also known for periods 8, 11, 12, 17, 24 and 60. | One of the most interesting aspects of the 2×2 rule is the large number of naturally-occurring higher-period oscillators. Oscillators with periods 3, 4, 5, 6, 10, 14, 22 and 26 are all relatively frequent, and oscillators are also known for periods 8, 11, 12, 17, 24 and 60. | ||
One simple infinite family of oscillators is given by the 2×(4n) boxes of alive [[cell]]s.<ref>{{Cite web|url=http://www.nathanieljohnston.com/index.php/2009/05/rectangular-oscillators-in-the-2x2-b36s125-cellular-automaton/|title=Rectangular Oscillators in the 2×2 (B36/S125) Cellular Automaton|author=Nathaniel Johnston|date=May 22, 2009|accessdate=May 24, 2009}}</ref> Such oscillators can be analyzed by noting that each [[phase]] of their oscillation can be represented as an exclusive or (XOR) of rectangles of different sizes that emulate the [[Rule 90]] cellular automaton.<ref>{{Cite web|url=http://groups.google.tk/group/comp.theory.cell-automata/browse_frm/thread/b059a5fb0c796743/c5683380affb8068?lnk=gst&q=2x2#c5683380affb8068|title=Life 2x2: long oscillator|publisher=comp.theory.cell-automata|accessdate=May 24, 2009|date=November 2, 2001}}</ref> The period of these oscillators for n = 1, 2, 3, ... is given by the sequence 2, 6, 14, 14, 62, 126, 30, 30, 1022, ... (Sloane's | {{EmbedViewer | ||
|pname = 2x2oscillators | |||
|position = center | |||
|caption = A [[stamp collection]] of oscillators with different periods from 2 through 60.<br> | |||
|viewerconfig = #C [[ THUMBSIZE 2 HEIGHT 720 WIDTH 960 ]] | |||
}} | |||
One simple infinite family of oscillators is given by the 2×(4n) boxes of alive [[cell]]s.<ref>{{Cite web|url=http://www.nathanieljohnston.com/index.php/2009/05/rectangular-oscillators-in-the-2x2-b36s125-cellular-automaton/|title=Rectangular Oscillators in the 2×2 (B36/S125) Cellular Automaton|author=Nathaniel Johnston|date=May 22, 2009|accessdate=May 24, 2009}}</ref> Such oscillators can be analyzed by noting that each [[phase]] of their oscillation can be represented as an exclusive or (XOR) of rectangles of different sizes that emulate the [[Rule 90]] cellular automaton.<ref>{{Cite web|url=http://groups.google.tk/group/comp.theory.cell-automata/browse_frm/thread/b059a5fb0c796743/c5683380affb8068?lnk=gst&q=2x2#c5683380affb8068|title=Life 2x2: long oscillator|publisher=comp.theory.cell-automata|accessdate=May 24, 2009|date=November 2, 2001}}</ref> The period of these oscillators for n = 1, 2, 3, ... is given by the sequence 2, 6, 14, 14, 62, 126, 30, 30, 1022, ... (Sloane's {{OEIS|A160657}}). | |||
====Naturally occurring oscillators==== | ====Naturally occurring oscillators==== | ||
Line 360: | Line 389: | ||
</td></tr></table> | </td></tr></table> | ||
{{EmbedViewer | |||
|pname = 2x2glider | |||
|position = right | |||
|caption = The c/8 glider ({{LinkCatagolue|xq8_2je4|rule=b36s125|style=brief}})<br> | |||
|viewerconfig = #C [[ AUTOSTART ZOOM 32 GPS 4 TRACKLOOP 8 -1/8 1/8 ]] | |||
}} | |||
===Spaceships=== | ===Spaceships=== | ||
There are a number of spaceships known to occur in 2×2.<ref>{{cite web|url=http://fano.ics.uci.edu/ca/rules/b36s125/ |title=2x2 (B36/S125) |publisher=David Eppstein|accessdate=March 18, 2009}}</ref> Of these, only one is known to occur naturally from [[soup]]. It travels at c/8 diagonally. | |||
===Infinite growth=== | ===Infinite growth=== | ||
[[ | The first known infinitely-growing pattern in 2×2 was discovered in June 2009 by [[Nathaniel Johnston]] while testing the [http://www.conwaylife.com/soup/ Online Life-Like CA Soup Search] -- a c/8 diagonal [[wickstretcher]] based on the above c/8 glider.<ref>{{Cite web|url=http://www.conwaylife.com/forums/viewtopic.php?f=2&t=114|title=First infinite growth in 2x2 (B36/S125)?|publisher=ConwayLife.com forums|accessdate=July 13, 2009}}</ref><ref>{{Cite web|url=http://www.nathanieljohnston.com/index.php/2009/07/the-online-life-like-ca-soup-search/|title=The Online Life-Like CA Soup Search|publisher=NathanielJohnston.com|date=July 11, 2009|accessdate=July 13, 2009}}</ref> Multiple c/2 [[puffers]] have been discovered by [[Paul Tooke]] in 2010 including p60 forward and backward c/8 glider [[rakes]], a 2c/5 [[puffer]] was also discovered. No [[gun]]s have yet been discovered in 2×2. An MMS [[breeder]] was [http://www.conwaylife.com/forums/viewtopic.php?f=11&t=39&start=25#p20740 discovered] by [[Arie Paap]] on June 25, 2015. | ||
{{EmbedViewer | |||
|pname = 2x2linepuffer | |||
|position = center | |||
|caption = The c/8 wickstretcher ({{LinkCatagolue|yl8_1_1_aae0a4678d7caeb6b463f7c082d8bd1a|rule=b36s125|style=brief|format=linear growth}})<br> | |||
|viewerconfig = #C [[ AUTOSTART X -2 Y 4 ZOOM 32 GPS 4 TRACKLOOP 8 -1/8 1/8 ]] | |||
}} | |||
== See also == | |||
*[[List of Life-like cellular automata]] | |||
*[[Flock]] | |||
==References== | ==References== | ||
<references /> | <references /> | ||
==Further reading== | |||
* [[Nathaniel Johnston]], ''[https://arxiv.org/abs/1203.1644 The B36/S125 "2x2" Life-Like Cellular Automaton]'', in: [[Andrew Adamatzky]] (ed.), ''Game of Life Cellular Automata'', Springer 2010, pp. 99-114 | |||
==External links== | |||
{{LinkForumThread|f=11|t=39|title=2x2}} | |||
{{LinkCatagolueRule|b36s125}} | |||
{{LinkEppsteinRule|b36s125}} |
Revision as of 14:55, 9 August 2019
2×2 | |
View static image | |
View animated image | |
Rulestring | 125/36 B36/S125 |
---|---|
Rule integer | 19528 |
Character | Chaotic |
Black/white reversal | B012458/S0134678 |
2×2 is a Life-like cellular automaton in which cells survive from one generation to the next if they have 1, 2 or 5 neighbours, and are born if they have 3 or 6 neighbours. It thus has rulestring "B36/S125". Patterns under the rule have a chaotic evolution similar to those under the standard Life rules, but the chaos tends to die out much more quickly.
Its name comes from the fact that patterns made up of 2×2 blocks continue to evolve as patterns made up of 2×2 blocks.
Block evolution
The 2×2 rule can emulate a simpler cellular automaton that acts on each 2×2 block. The emulated automaton is a block cellular automaton that makes use of the Margolus neighbourhood and evolves according to the following six rules:
Note that, as this emulates a Margolus neighbourhood, the resulting block appears at the center of the original four blocks. Thus, patterns that are originally made up of 2×2 blocks will forever be made up of 2×2 blocks, but the block partition will be offset by one cell in the odd generations from the even generations. By examining the image above, one can see that a Life-like cellular automaton will emulate a Margolus block cellular automaton if and only if the following four equations are satisfied: B4 = S4, B5 = S6 = S7, B3 = S5, B1 = B2 = S3, where the first equation for example means that the birth condition for cells with four neighbours must equal the survival condition for cells with four neighbours. There are 212 = 4096 such rules, which emulate 26 = 64 different block cellular automata. Any arrangement of cells that fits within a 2x2 bounding box can simulate these using isotropic non-totalistic rules.
This rule can be seen to satisfy the above equations because 4 is neither a birth condition nor a survival condition, 5 is not a birth condition and 6 and 7 are not survival conditions, 3 is a birth condition and 5 is a survival condition, and 3 is not a survival condition and 1 and 2 are not birth conditions.
The non-totalistic Life-like cellular automaton B3i4int5ey6k7e/S1e2k3ey4irt5i can be used to simulate this rule. 1x1 cells simulate the clusters of 2x2 blocks, and only every second generation plays, since odd generations have the offset.
Notable patterns
A large variety of still lifes and oscillators appear spontaneously from randomly generated starting states. There is also a somewhat rare naturally-occurring spaceship, which travels at c/8 diagonally.
Still lifes
Still lifes are generally smaller in 2×2 than in Life, with the smallest occurring having a population of just 2 cells. These still life patterns still tend to be similar to Life patterns in terms of structure, for example often having islands that stabilise each other. Many still lifes from Life are also still lifes in 2×2, For example, the beehive, tub, loaf, pond and mango.
Some sample still lifes. (click above to open LifeViewer) RLE: here Plaintext: here |
Enumerating still lifes
The following table catalogs all still lifes in the 2x2 rule with 10 or fewer cells.[1]
Size | Count | Image | Links |
---|---|---|---|
1 | 0 | ||
2 | 2 | Download RLE: click here | |
3 | 1 | Download RLE: click here | |
4 | 3 | Download RLE: click here | |
5 | 4 | Download RLE: click here | |
6 | 9 | Download RLE: click here | |
7 | 10 | Download RLE: click here | |
8 | 27 | Download RLE: click here | |
9 | 48 | Download RLE: click here | |
10 | 126 | Download RLE: click here |
Common still lifes
The following table lists the twenty most common strict still lifes that arise after several generations of a random starting pattern.[2] The "approx. rel. freq." column gives an estimate of the proportion of all randomly-occurring still lifes that will be of the given type.
|
|
Oscillators
A large variety of oscillators of various periods occur naturally in 2×2.
Period two oscillators
Many of the period 2 oscillators in 2×2 have a single-cell 'on-off' rotor, with small variations in the stator of the oscillator. These occur fairly frequently naturally.
Some period 2 oscillators. (click above to open LifeViewer) RLE: here Plaintext: here |
Higher-period oscillators
One of the most interesting aspects of the 2×2 rule is the large number of naturally-occurring higher-period oscillators. Oscillators with periods 3, 4, 5, 6, 10, 14, 22 and 26 are all relatively frequent, and oscillators are also known for periods 8, 11, 12, 17, 24 and 60.
A stamp collection of oscillators with different periods from 2 through 60. (click above to open LifeViewer) RLE: here Plaintext: here |
One simple infinite family of oscillators is given by the 2×(4n) boxes of alive cells.[3] Such oscillators can be analyzed by noting that each phase of their oscillation can be represented as an exclusive or (XOR) of rectangles of different sizes that emulate the Rule 90 cellular automaton.[4] The period of these oscillators for n = 1, 2, 3, ... is given by the sequence 2, 6, 14, 14, 62, 126, 30, 30, 1022, ... (Sloane's A160657).
Naturally occurring oscillators
The following table lists the twenty most common oscillators that arise after several generations of a random starting pattern.[2] Of particular interest are some quite high-period oscillators that appear abnormally frequently (in particular, the period 26 stairstep hexomino is the third most common oscillator). The "approx. rel. freq." column gives an estimate of the proportion of all randomly-occurring oscillators that will be of the given type.
|
|
Spaceships
There are a number of spaceships known to occur in 2×2.[5] Of these, only one is known to occur naturally from soup. It travels at c/8 diagonally.
Infinite growth
The first known infinitely-growing pattern in 2×2 was discovered in June 2009 by Nathaniel Johnston while testing the Online Life-Like CA Soup Search -- a c/8 diagonal wickstretcher based on the above c/8 glider.[6][7] Multiple c/2 puffers have been discovered by Paul Tooke in 2010 including p60 forward and backward c/8 glider rakes, a 2c/5 puffer was also discovered. No guns have yet been discovered in 2×2. An MMS breeder was discovered by Arie Paap on June 25, 2015.
The c/8 wickstretcher (Catagolue: here) (click above to open LifeViewer) RLE: here Plaintext: here |
See also
References
- ↑ Computed using the EnumStillLifes.c script located here.
- ↑ 2.0 2.1 Full results are located here.
- ↑ Nathaniel Johnston (May 22, 2009). "Rectangular Oscillators in the 2×2 (B36/S125) Cellular Automaton". Retrieved on May 24, 2009.
- ↑ "Life 2x2: long oscillator". comp.theory.cell-automata (November 2, 2001). Retrieved on May 24, 2009.
- ↑ "2x2 (B36/S125)". David Eppstein. Retrieved on March 18, 2009.
- ↑ "First infinite growth in 2x2 (B36/S125)?". ConwayLife.com forums. Retrieved on July 13, 2009.
- ↑ "The Online Life-Like CA Soup Search". NathanielJohnston.com (July 11, 2009). Retrieved on July 13, 2009.
Further reading
- Nathaniel Johnston, The B36/S125 "2x2" Life-Like Cellular Automaton, in: Andrew Adamatzky (ed.), Game of Life Cellular Automata, Springer 2010, pp. 99-114
External links
- 2x2 (discussion thread) at the ConwayLife.com forums
2×2 at Adam P. Goucher's Catagolue 2×2 at David Eppstein's Glider Database