Difference between revisions of "Unit cell"
Jump to navigation
Jump to search
m (Typo) |
m (Standardized references, and de-referencify some that aren't actually references) |
||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
A '''unit cell''' 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 1x1. 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''' 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 1x1. 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 [https://en.wikipedia.org/wiki/Rule_54 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 == | ||
The [[p5760 unit Life cell|first unit Life cell]] was constructed by [[David Bell]] in [[:Category:Patterns found in 1996|1996]].<ref>{{cite web|url=http://radicaleye.com/lifepage/patterns/unitcell/ucdesc.html|title=The Unit Life Cell|author=Paul Callahan|date=March 1, 1996}}</ref> 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]]".<ref>{{cite web|url=http://www.physicsforums.com/showthread.php?t=45061|title=Game of Life Deep Cell|author=Jared Prince|date=September 27, 2004}}</ref> | The [[p5760 unit Life cell|first unit Life cell]] was constructed by [[David Bell]] in [[:Category:Patterns found in 1996|1996]].<ref>{{cite web|url=http://radicaleye.com/lifepage/patterns/unitcell/ucdesc.html|title=The Unit Life Cell|author=Paul Callahan|date=March 1, 1996}}</ref> 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]]".<ref>{{cite web|url=http://www.physicsforums.com/showthread.php?t=45061|title=Game of Life Deep Cell|author=Jared Prince|date=September 27, 2004}}</ref> | ||
More recently [[OTCA metapixel]] was constructed that simulates any [[Life-like cellular automaton]].<ref>{{cite web|url=http://otcametapixel.blogspot.com/|title=OTCAmetapixel}}</ref> Designed to run quickly in [[HashLife]], it has the advantage of having two states that are clearly distinct when zoomed out. | More recently the [[OTCA metapixel]] was constructed that simulates any [[Life-like cellular automaton]].<ref>{{cite web|url=http://otcametapixel.blogspot.com/2006/05/how-does-it-work.html/|title=How Does It Work?|work=OTCAmetapixel|author=Brice Due|date=May 28, 2006|accessdate=March 26, 2009}}</ref> Designed to run quickly in [[HashLife]], it has the advantage of having two states that are clearly distinct when zoomed out. | ||
The [[P1 megacell]] is currently the largest unit cell. Like the OTCA metapixel, it has clearly visible states. 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 [[P1 megacell]] is currently the largest unit cell. Like the OTCA metapixel, it has clearly visible states. 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. | ||
| Line 15: | Line 15: | ||
=== 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 [https://en.wikipedia.org/wiki/Rule_110 Rule 110] and allegedly [https://en.wikipedia.org/wiki/Rule_30 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=New spaceship velocity|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 life-like rules with constructed W110 unit cells ==== | ==== Selection of life-like rules with constructed W110 unit cells ==== | ||
* B3[8]/S23[8] polyglot | * B3[8]/S23[8] polyglot: works in [[Life]], [[EightLife]], [[Pedestrian Life]] and [[HoneyLife]]<ref name="post53026" /> | ||
* Banks-I | * Banks-I: proves logic universality using Cook's results, simplifying Banks' proofs from 1971<ref name="post52584" /> | ||
* B35/S236<ref | * B35/S236<ref name="post52043" /> | ||
* [[DryLife]] and 3 more<ref | * [[DryLife]] and 3 more<ref name="post58579" /> | ||
==References== | ==References== | ||
<references /> | <references> | ||
<ref name="post53026">{{LinkForumThread | |||
|format = ref | |||
|title = FWSS-less MWSS-track-only Rule-110 Unit Cell | |||
|p = 53026 | |||
|author = Peter Naszvadi | |||
|date = November 21, 2017 | |||
}}</ref> | |||
<ref name="post52584">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 52584 | |||
|author = Peter Naszvadi | |||
|date = November 1, 2017 | |||
}}</ref> | |||
<ref name="post52043">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 52043 | |||
|author = Peter Naszvadi | |||
|date = October 14, 2017 | |||
}}</ref> | |||
<ref name="post58579">{{LinkForumThread | |||
|format = ref | |||
|title = Re: List of the Turing-complete totalistic life-like CA | |||
|p = 58579 | |||
|author = Peter Naszvadi | |||
|date = March 29, 2018 | |||
}}</ref> | |||
</references> | |||
==External Links== | ==External Links== | ||
{{LinkWeisstein|UnitLifeCell.html|patternname=Unit Life cell}} | {{LinkWeisstein|UnitLifeCell.html|patternname=Unit Life cell}} | ||
{{LinkLexicon|lex_u.htm#unitlifecell}} | {{LinkLexicon|lex_u.htm#unitlifecell}} | ||
Revision as of 04:28, 16 February 2019
A unit cell 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 1x1. 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]
More recently the OTCA metapixel was constructed that simulates 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 is currently the largest unit cell. Like the OTCA metapixel, it has clearly visible states. 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.
Simulating a 1D cellular automaton
Natural occurrences
Many replicators also act as a one-dimensional cellular automaton, for example the replicator in HighLife.
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[4] 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[5]
- Banks-I: proves logic universality using Cook's results, simplifying Banks' proofs from 1971[6]
- B35/S236[7]
- DryLife and 3 more[8]
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.
- ↑ Hienrich Koenig (December 21, 2005). "New spaceship velocity". 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
External Links
- Unit cell at the Life Lexicon