Difference between revisions of "Unit cell"
(Adding first W110 tiny replicator) |
(since there seems to be no other list on the wiki) |
||
| (6 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
A '''unit cell''' (or '''metacell''') is a subset (usually rectangular or square) of the Life plane that tiles over the plane, along with a fixed number of distinct patterns, with each tile assuming one of the patterns, such that it simulates a [[cellular automaton]], possibly itself. A '''unit Life cell''' is a unit cell that simulates the [[Conway's Game of Life|Game of Life]]. To avoid single [[cell]]s themselves being considered unit cells, the size of a unit cell must be greater than 1×1. It is also a restriction that only finite sized patterns are accepted as unit cells excluding infinite one-cell thick bars in [[HighLife]] for example, which simulates [ | A '''unit cell''' (or '''metacell''') is a subset (usually rectangular or square) of the Life plane that tiles over the plane, along with a fixed number of distinct patterns, with each tile assuming one of the patterns, such that it simulates a [[cellular automaton]], possibly itself. A '''unit Life cell''' is a unit cell that simulates the [[Conway's Game of Life|Game of Life]]. To avoid single [[cell]]s themselves being considered unit cells, the size of a unit cell must be greater than 1×1. It is also a restriction that only finite sized patterns are accepted as unit cells excluding infinite one-cell thick bars in [[HighLife]] for example, which simulates [[Rule 54]]; many [[amphichiral]] 1D elementary automata can be embedded in other rules via this method. | ||
== Simulating a 2D cellular automaton == | == Simulating a 2D cellular automaton == | ||
| Line 14: | Line 14: | ||
=== Natural occurrences === | === Natural occurrences === | ||
Most replicators can be described as simulating a one-dimensional cellular automaton. For example, the [[replicator]] in [[HighLife]] can be described as simulating Rule 90 (for the 3-cell neighbourhood, or Rule 6 for the two-cell, range-1/2 neighbourhood). | |||
Interestingly, the U-pentomino is a period 8 natural replicator that emulates [ | Certain basic infinite-growth patterns could arguably be considered replicators that simulate rules such as [https://www.conwaylife.com/forums/viewtopic.php?f=11&t=2238&p=50033#p50033 Rule 50] and [https://www.conwaylife.com/forums/viewtopic.php?f=11&t=2238&p=50033#p50392 Rule 254]. | ||
Interestingly, the U-pentomino is a period 8 natural replicator that emulates [[Rule 110]] in rules between B2ei3aci4aei5kqr7e/S01c2-kn3ijry4citwy5aeiq and B2ein3acikq4-jrty5-ceiy6-ck78/S01c2-k3-acen4-a5-jny6-c78. This pattern was found by iNoMed<ref name="post116434" /> and got 2nd place at the [[OCA Discovery of the Year#2020|OCA Discovery of the Year]] contest. In the 1st of January 2021, AforAmpere found<ref name="post117657" /> a faster one, the T-tetromino with period 2 in rules supporting rules from B2ai3aeir4r5ei/S3e5e6i to B2-c34-i56-i78/S2-ai3-i4-e5678. | |||
So far, the following 1D rules are known: | |||
* Rule 0<ref name="thebigone"/> | |||
* Rule 2<ref name="thebigone"/> | |||
* Rule 4<ref name="thebigone"/> | |||
* Rule 16<ref name="thebigone"/> | |||
* Rule 22<ref name="thebigone"/> | |||
* Rule 32<ref name="thebigone"/> | |||
* Rule 50<ref name="thebigone"/> | |||
* Rule 90<ref name="thebigone"/> | |||
* Rule 110<ref name="post116434" /><ref name="post117657" /> | |||
* Rule 128<ref name="thebigone"/> | |||
* Rule 150<ref name="thebigone"/> | |||
* Rule 254<ref name="thebigone"/> | |||
Rules of larger ranges are also known: | |||
* Rule W1208925819614629174771760<ref name="thebigone"/> | |||
=== Constructions === | === Constructions === | ||
Complex one-dimensional cellular automata usually can be simulated via constructed unit cells. Purpose of this is basically the containing automaton inherits some useful properties of the embedded, which is usually not trivial to prove. Such properties are logic universality, Turing-completeness etc. It is known that many examples are constructed in order to simulate [ | Complex one-dimensional cellular automata usually can be simulated via constructed unit cells. Purpose of this is basically the containing automaton inherits some useful properties of the embedded, which is usually not trivial to prove. Such properties are logic universality, Turing-completeness etc. It is known that many examples are constructed in order to simulate [[Rule 110]] and allegedly [[Rule 30]] in one case. One is constructed in CGoL by [[Jason Summers]]<ref>{{Cite web|url=http://pentadecathlon.com/lifenews/2005/12/rule_110_unit_cell.html|title="Rule 110" Unit Cell|work=Game of Life News|author=Hienrich Koenig|date=December 21, 2005|accessdate=March 29, 2018}}</ref> and later it was trivially shown using [[Golly]] that it is a polyglot (works in [[EightLife]], too) | ||
==== Selection of | ==== Selection of Life-like rules with constructed W110 unit cells ==== | ||
* B3[8]/S23[8] polyglot: works in [[Life]], [[EightLife]], [[Pedestrian Life]] and [[HoneyLife]]<ref name="post53026" /> | * B3[8]/S23[8] polyglot: works in [[Life]], [[EightLife]], [[Pedestrian Life]] and [[HoneyLife]]<ref name="post53026" /> | ||
* Banks-I: proves logic universality using Cook's results, simplifying Banks' proofs from 1971<ref name="post52584" /> | * [[Banks-I]]: proves logic universality using Cook's results, simplifying Banks' proofs from 1971<ref name="post52584" /> | ||
* B35/S236<ref name="post52043" /> | * B35/S236<ref name="post52043" /> | ||
* [[DryLife]] and 3 more<ref name="post58579" /> | * [[DryLife]] and 3 more<ref name="post58579" /> | ||
* [[2×2]]<ref name="post121769" /> | |||
* [[Move]]<ref name="post102550" /> | |||
* B36[8]/S236[8] polyglot: [[HighLife]], [[LowDeath]], and others<ref name="post62217" /> | |||
* [[Life without death]]<ref name="post106546" /> | |||
* [[Live Free or Die]]<ref name="post107139" /> | |||
* [[Day & Night]]<ref name="post102258" /> | |||
* [[Seeds]]<ref name="post108522" /> | |||
* [[DotLife]] using a two-dimensional emulator<ref name="post117425" /> | |||
* [[Brian's Brain]]<ref name="post110762" /> | |||
* [[Logarithmic replicator rule]]<ref name="post102490" /> | |||
* [[Star Wars]] using a cyclical emulator<ref name="post111232" /> | |||
==References== | ==References== | ||
| Line 70: | Line 100: | ||
|author = AforAmpere | |author = AforAmpere | ||
|date = January 1, 2021 | |date = January 1, 2021 | ||
}}</ref> | |||
<ref name="thebigone">{{LinkForumThread | |||
|format = ref | |||
|title = Replicators and other patterns that simulate even 1D rules | |||
|p = 61459 | |||
|author = muzik | |||
|date = June 29, 2018 | |||
}}</ref> | |||
<ref name="post121769">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 121769 | |||
|author = FWKnightship | |||
|date = February 4, 2021 | |||
}}</ref> | |||
<ref name="post102550">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 102550 | |||
|author = Layz Boi | |||
|date = August 20, 2020 | |||
}}</ref> | |||
<ref name="post62217">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 62217 | |||
|author = Peter Naszvadi | |||
|date = July 29, 2018 | |||
}}</ref> | |||
<ref name="post106546">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 106546 | |||
|author = Peter Naszvadi | |||
|date = October 13, 2020 | |||
}}</ref> | |||
<ref name="post107139">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 107139 | |||
|author = FWKnightship | |||
|date = October 20, 2020 | |||
}}</ref> | |||
<ref name="post102258">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 102258 | |||
|author = Peter Naszvadi | |||
|date = August 14, 2020 | |||
}}</ref> | |||
<ref name="post108522">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 108522 | |||
|author = Peter Naszvadi | |||
|date = October 30, 2020 | |||
}}</ref> | |||
<ref name="post117425">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 117425 | |||
|author = FWKnightship | |||
|date = December 30, 2020 | |||
}}</ref> | |||
<ref name="post110762">{{LinkForumThread | |||
|p = 110762 | |||
|format = ref | |||
|title = Re: Turing - complete Generations rules | |||
|author = Yoel Matveyev | |||
|date = November 15, 2020 | |||
}}</ref> | |||
<ref name="post102490">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 102490 | |||
|author = Peter Naszvadi | |||
|date = August 19, 2020 | |||
}}</ref> | |||
<ref name="post111232">{{LinkForumThread | |||
|p = 111232 | |||
|format = ref | |||
|title = Re: Star Wars Rule | |||
|author = FWKnightship | |||
|date = November 18, 2020 | |||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
Revision as of 18:29, 5 May 2021
A unit cell (or metacell) is a subset (usually rectangular or square) of the Life plane that tiles over the plane, along with a fixed number of distinct patterns, with each tile assuming one of the patterns, such that it simulates a cellular automaton, possibly itself. A unit Life cell is a unit cell that simulates the Game of Life. To avoid single cells themselves being considered unit cells, the size of a unit cell must be greater than 1×1. It is also a restriction that only finite sized patterns are accepted as unit cells excluding infinite one-cell thick bars in HighLife for example, which simulates Rule 54; many amphichiral 1D elementary automata can be embedded in other rules via this method.
Simulating a 2D cellular automaton
The first unit Life cell was constructed by David Bell in 1996.[1] It employs standard glider logic to determine whether or not a glider should be present. The two states differ by a single glider. In 2004, Jared Prince modified David Bell's unit Life cell to support two (and therefore multiple) layers of Life universes, coined "deep cell".[2]
Around 2005, the OTCA metapixel was constructed, which can simulate any Life-like cellular automaton.[3] Designed to run quickly in HashLife, it has the advantage of having two states that are clearly distinct when zoomed out.
The P1 megacell, designed in 2008, has clearly visible states like the OTCA metapixel. It is capable of simulating any rule, including non-totalistic and asymmetric rules, that uses the standard eight-cell neighborhood. It also has unusual positioning, being a square with diagonal edges. This allows much of its information to be transmitted with gliders.
The 0E0P metacell is currently the largest unit cell. Unlike other unit cells, it can function without any form of support circuitry, allowing it to produce the first examples of exotic patterns such as parity-rule replicators and reflectorless rotating oscillators in Life when programmed correctly. Rather than having an "on" state or an "off" state, it deconstructs itself when it turns off and is built by its neighbors when it is turned on.
Simulating a 1D cellular automaton
Natural occurrences
Most replicators can be described as simulating a one-dimensional cellular automaton. For example, the replicator in HighLife can be described as simulating Rule 90 (for the 3-cell neighbourhood, or Rule 6 for the two-cell, range-1/2 neighbourhood).
Certain basic infinite-growth patterns could arguably be considered replicators that simulate rules such as Rule 50 and Rule 254.
Interestingly, the U-pentomino is a period 8 natural replicator that emulates Rule 110 in rules between B2ei3aci4aei5kqr7e/S01c2-kn3ijry4citwy5aeiq and B2ein3acikq4-jrty5-ceiy6-ck78/S01c2-k3-acen4-a5-jny6-c78. This pattern was found by iNoMed[4] and got 2nd place at the OCA Discovery of the Year contest. In the 1st of January 2021, AforAmpere found[5] a faster one, the T-tetromino with period 2 in rules supporting rules from B2ai3aeir4r5ei/S3e5e6i to B2-c34-i56-i78/S2-ai3-i4-e5678.
So far, the following 1D rules are known:
- Rule 0[6]
- Rule 2[6]
- Rule 4[6]
- Rule 16[6]
- Rule 22[6]
- Rule 32[6]
- Rule 50[6]
- Rule 90[6]
- Rule 110[4][5]
- Rule 128[6]
- Rule 150[6]
- Rule 254[6]
Rules of larger ranges are also known:
- Rule W1208925819614629174771760[6]
Constructions
Complex one-dimensional cellular automata usually can be simulated via constructed unit cells. Purpose of this is basically the containing automaton inherits some useful properties of the embedded, which is usually not trivial to prove. Such properties are logic universality, Turing-completeness etc. It is known that many examples are constructed in order to simulate Rule 110 and allegedly Rule 30 in one case. One is constructed in CGoL by Jason Summers[7] and later it was trivially shown using Golly that it is a polyglot (works in EightLife, too)
Selection of Life-like rules with constructed W110 unit cells
- B3[8]/S23[8] polyglot: works in Life, EightLife, Pedestrian Life and HoneyLife[8]
- Banks-I: proves logic universality using Cook's results, simplifying Banks' proofs from 1971[9]
- B35/S236[10]
- DryLife and 3 more[11]
- 2×2[12]
- Move[13]
- B36[8]/S236[8] polyglot: HighLife, LowDeath, and others[14]
- Life without death[15]
- Live Free or Die[16]
- Day & Night[17]
- Seeds[18]
- DotLife using a two-dimensional emulator[19]
- Brian's Brain[20]
- Logarithmic replicator rule[21]
- Star Wars using a cyclical emulator[22]
References
- ↑ Paul Callahan (March 1, 1996). "The Unit Life Cell".
- ↑ Jared Prince (September 27, 2004). "Game of Life Deep Cell".
- ↑ Brice Due (May 28, 2006). "How Does It Work?". OTCAmetapixel. Retrieved on March 26, 2009.
- ↑ 4.0 4.1 toroidalet (December 19, 2020). Re: Rules with interesting replicators (discussion thread) at the ConwayLife.com forums
- ↑ 5.0 5.1 AforAmpere (January 1, 2021). Re: Rules with interesting replicators (discussion thread) at the ConwayLife.com forums
- ↑ 6.00 6.01 6.02 6.03 6.04 6.05 6.06 6.07 6.08 6.09 6.10 6.11 muzik (June 29, 2018). Replicators and other patterns that simulate even 1D rules (discussion thread) at the ConwayLife.com forums
- ↑ Hienrich Koenig (December 21, 2005). ""Rule 110" Unit Cell". Game of Life News. Retrieved on March 29, 2018.
- ↑ Peter Naszvadi (November 21, 2017). FWSS-less MWSS-track-only Rule-110 Unit Cell (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (November 1, 2017). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (October 14, 2017). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (March 29, 2018). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ FWKnightship (February 4, 2021). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Layz Boi (August 20, 2020). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (July 29, 2018). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (October 13, 2020). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ FWKnightship (October 20, 2020). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (August 14, 2020). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (October 30, 2020). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ FWKnightship (December 30, 2020). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ Yoel Matveyev (November 15, 2020). Re: Turing - complete Generations rules (discussion thread) at the ConwayLife.com forums
- ↑ Peter Naszvadi (August 19, 2020). Re: List of the Turing-complete totalistic life-like CA (discussion thread) at the ConwayLife.com forums
- ↑ FWKnightship (November 18, 2020). Re: Star Wars Rule (discussion thread) at the ConwayLife.com forums
External links
- Unit cell at the Life Lexicon
- Metacell at the Life Lexicon