Difference between revisions of "0E0P metacell"
m (LifeViewer) |
m (formatting) |
||
(26 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
{{UnitCell | {{UnitCell | ||
|name = 0E0P metacell | |name = 0E0P metacell | ||
Line 15: | Line 14: | ||
The '''0E0P metacell''' is a [[unit cell]] constructed by [[Adam P. Goucher]] between 2014 and 2018.<ref>{{cite web|url=https://cp4space.wordpress.com/2018/11/12/fully-self-directed-replication/ |title=Fully Self-Directed Replication |publisher=Adam P. Goucher |date=November 12, 2018|accessdate=January 8, 2019}}</ref> Like Goucher's previous [[p1 megacell]], it is capable of simulating any [[rule]] using the [[Moore neighborhood|standard eight cell neighborhood]], including [[non-totalistic rule]]s. | The '''0E0P metacell''' is a [[unit cell]] constructed by [[Adam P. Goucher]] between 2014 and 2018.<ref>{{cite web|url=https://cp4space.wordpress.com/2018/11/12/fully-self-directed-replication/ |title=Fully Self-Directed Replication |publisher=Adam P. Goucher |date=November 12, 2018|accessdate=January 8, 2019}}</ref> Like Goucher's previous [[p1 megacell]], it is capable of simulating any [[rule]] using the [[Moore neighborhood|standard eight cell neighborhood]], including [[non-totalistic rule]]s. | ||
The new feature of the 0E0P metacell, and the one that explains its record-breaking large size, is the fact that a group of these metacells can be placed in an empty Life universe with no background grid of OFF metacells, and the entire universe then simulates the rule for which the 0E0P metacells are programmed, at a larger scale by a factor of 262144 | The new feature of the 0E0P metacell, and the one that explains its record-breaking large size, is the fact that a group of these metacells can be placed in an empty Life universe with no background grid of OFF metacells, and the entire universe then simulates the rule for which the 0E0P metacells are programmed, at a larger scale by a factor of {{eq|262144|2{{sup|18}}}}. The acronym "0E0P" is short for "[State] Zero Encoded by Zero Population", so the OFF state is simply a metacell-sized region of empty space. | ||
When one of these metacells turns off, it self-destructs completely, and when a metacell birth occurs, it must be constructed from the ground up by one of its neighbors. This allows 0E0P metacell patterns, when viewed from very far away (e.g., at a size where an entire metacell takes up a single pixel in the display), to be indistinguishable from normal patterns that use the same rule -- except that the metacell patterns will run 2 | When one of these metacells turns off, it self-destructs completely, and when a metacell birth occurs, it must be constructed from the ground up by one of its neighbors. This allows 0E0P metacell patterns, when viewed from very far away (e.g., at a size where an entire metacell takes up a single pixel in the display), to be indistinguishable from normal patterns that use the same rule -- except that the metacell patterns will run 2{{sup|36}} times more slowly, and if they're run at a step size lower than 2{{sup|36}}, intermediate states may be visible that will depart from a strict pixel-for-pixel match. | ||
The {{POTY|year=2018|rank=2|behind=[[Sir Robin]]}} | |||
==Details== | ==Details== | ||
Each individual metacell behaves as an 8-state, 4-neighborhood BCC-automaton; the metacell receives a glider-based signal (a positive integer between 1 and 7, inclusive) from each of its (up to four) neighbours, and a 0 from any empty spaces if there are fewer than four neighbours. It then computes the quantity 8 | Each individual metacell behaves as an 8-state, 4-neighborhood BCC-automaton; the metacell receives a glider-based signal (a positive integer between 1 and 7, inclusive) from each of its (up to four) neighbours, and a 0 from any empty spaces if there are fewer than four neighbours. It then computes the quantity {{nowrap|8{{sup|3}} a + 8{{sup|2}} b + 8{{sup|1}} c + d}}, where {{nowrap|(a, b, c, d)}} are the four input signals, and indexes into a 4096-element lookup table to retrieve a value between 0 and 7 (the new ‘state’ of the metacell). If 0, it immediately self-destructs without constructing any children; if nonzero, it constructs a daughter machine in each vacant space. Finally, it broadcasts the new state as a signal to all four neighbours, before self-destructing. In doing so, the metacell behaves as a single cell in any 8-state 4-neighbor cellular automaton; as every 2-state 9-neighbour cellular automaton can be emulated at half the speed as an 8-state 4-neighbour cellular automaton, this allows the 0E0P metacell to emulate rules other than Life, which also allows it to act as a parity-rule [[replicator]], a [[reflectorless rotating oscillator]] (with some limits), and a [[SMOS]] if programmed correctly. | ||
In a healthy 0E0P metacell pattern, metacells could be thought of as living on a diagonally-oriented checkerboard. They're allowed to be present on the dark squares of the checkerboard '''only''' during even 2{{sup|35}}-tick half-cycles, and on the light squares of the checkerboard only during odd half-cycles. At the beginning of each even half-cycle, or in other words at the beginning of each full metatick, the presence or absence of an 0E0P metacell on a dark square corresponds with the presence or absence of an ON cell in an equivalent Life grid (assuming the metacell is programmed to emulate B3/S23). At other times during the 0E0P's replication cycle, the correspondence with cells on a Life grid won't be as clean, but every 2{{sup|36}} ticks the 0E0P metapattern will come back into perfect alignment. | |||
Every period-2{{sup|36}} cycle of an 0E0P metacell consists of two period-2{{sup|35}} half-cycles. In each half-cycle, all metacells make sure that there are child metacells all around them, on the other checkerboard square color -- either by building them, or by attempting to build them and having the construction recipe cleanly eaten by an eater that's part of an already existing child in that location. | |||
Notice that with the 45-degree checkerboard orientation, each grid location in the emulated Life pattern is only half filled by a 0E0P metacell (if one is present). In other words, the metacells are diamond-shaped, not square; their sides don't line up with the emulated Life grid. | |||
Switching checkerboard colors and expanding to four surrounding metacells twice (for two half-cycles) effectively ensures that all eight metacells surrounding any given ON metacell on the same checkerboard square color are occupied by child metacells. These are all the neighbor locations for that particular metacell. No effect can travel faster than lightspeed in the range-1 Moore-neighborhood rules that the 0E0P metacell can emulate, so at the end of two half-cycles, metacells are present in every location where a metacell could possibly be needed to turn ON in the next metatick. | |||
There's no direct communication between an 0E0P metacell and its nearest possible living neighbor metacells to the north, south, east, and west -- i.e., the nearest same-color squares on the 45-degree-angled checkerboard -- let alone between it and the other possibly-living neighbor cells, two checkerboard squares away diagonally. However, by the end of each full cycle, communication between parent and child metacells during each half-cycle has effectively transmitted neighbor state information from one dark-square metacell to all its dark-square neighbors. This means that at the end of each half-cycle, every "potentially alive" 0E0P metacell has all the information it needs to decide whether it should transition to a "fully alive" state and start building child metacells, or if it should immediately self-destruct instead. | |||
To demonstrate | ==LifeViewer demo== | ||
To demonstrate the full 0E0P metacell cycle and the early self-destruct option, the [[LifeViewer]] demo below shows how a glider made of metacells proceeds through a full 2{{sup|36}} period (or "metatick"). Note that the gap between metacells where the equivalent cells would be diagonally adjacent will not be visible at the proper zoom level. | |||
{{LV:Viewer|x = 233, y = 233, rule = none | {{LV:Viewer|x = 233, y = 233, rule = none | ||
206.I$205.3I$204.5I$203.7I$202.3IEIE3I$201.3IEIEIE3I$200.5IEIEIE3I$ | 206.I$205.3I$204.5I$203.7I$202.3IEIE3I$201.3IEIEIE3I$200.5IEIEIE3I$ | ||
Line 110: | Line 120: | ||
#C [[ LABEL 230 30 16 "The five remaining metacells move to Stage E (purple).\nEmpty background locations are shown in green." ]] | #C [[ LABEL 230 30 16 "The five remaining metacells move to Stage E (purple).\nEmpty background locations are shown in green." ]] | ||
#C [[ POI INITIAL X 132 Y -108 Z 32 POITRANS 0 ]] POI #23 (initial position, because of INITIAL keyword) | #C [[ POI INITIAL X 132 Y -108 Z 32 POITRANS 0 ]] POI #23 (initial position, because of INITIAL keyword) | ||
#C [[ LABEL 245 6 16 "Press 'J' | #C [[ LABEL 245 6 16 "Press 'J' or 'Shift+J' keys, or < and > buttons,\nto move forward or backward through 0E0P stages." WIDTH 640 ]]}} | ||
==Complexity== | |||
The metacell's circuitry is sufficiently complex that a single Conway's Life meta-[[glider]] requires a compressed pattern file several megabytes in size.<ref name="post65737" /> It can be run in Golly at small step sizes with no difficulty, but simulating an entire replication cycle (half a metatick) is very difficult. On current computers it might take about half a CPU-year using Golly's standard HashLife algorithm. | |||
An order of magnitude improvement over [[HashLife]] is available via Goucher's special-purpose [[StreamLife]] algorithm. However, even using StreamLife it might take several months to simulate the eight replication cycles (four full metaticks) needed to return a metaglider to its original phase. The original experimental verification of a single metatick (12:05 to 12:35 in Cabaret's video below), using rule where a single ON cell is a still life, took about a month. | |||
==Videos== | ==Videos== | ||
{{#ev:youtube|CfRSVPhzN5M|640|left|Thomas Cabaret's video explaining various self-replicating machines in cellular automata, including a comprehensive explanation (from 7:35 to 13:05) of the operation of the 0E0P metacell}} | {{#ev:youtube|CfRSVPhzN5M|640|left|Thomas Cabaret's video explaining various self-replicating machines in cellular automata, including a comprehensive explanation (from 7:35 to 13:05) of the operation of the 0E0P metacell}} | ||
<!-- do not remove whitespace, this is needed for correct format --> | |||
== References == | == References == | ||
Line 131: | Line 170: | ||
}}</ref> | }}</ref> | ||
</references> | </references> | ||
[[Category:Patterns with between 10,000,000 and 99,999,999 cells]] |
Latest revision as of 06:34, 17 April 2023
0E0P metacell | ||
View static image | ||
Pattern type | Unit cell | |
---|---|---|
Number of cells | ~ 18650000 | |
Bounding box | 261841 × 261841 | |
Cell size | 262144 × 262144 | |
Period | 68719476736 | |
Discovered by | Adam P. Goucher | |
Year of discovery | 2018 |
The 0E0P metacell is a unit cell constructed by Adam P. Goucher between 2014 and 2018.[1] Like Goucher's previous p1 megacell, it is capable of simulating any rule using the standard eight cell neighborhood, including non-totalistic rules.
The new feature of the 0E0P metacell, and the one that explains its record-breaking large size, is the fact that a group of these metacells can be placed in an empty Life universe with no background grid of OFF metacells, and the entire universe then simulates the rule for which the 0E0P metacells are programmed, at a larger scale by a factor of 262144 = 218. The acronym "0E0P" is short for "[State] Zero Encoded by Zero Population", so the OFF state is simply a metacell-sized region of empty space.
When one of these metacells turns off, it self-destructs completely, and when a metacell birth occurs, it must be constructed from the ground up by one of its neighbors. This allows 0E0P metacell patterns, when viewed from very far away (e.g., at a size where an entire metacell takes up a single pixel in the display), to be indistinguishable from normal patterns that use the same rule -- except that the metacell patterns will run 236 times more slowly, and if they're run at a step size lower than 236, intermediate states may be visible that will depart from a strict pixel-for-pixel match.
The 0E0P metacell ranked second place in the Pattern of the Year 2018 competition on the ConwayLife.com forums, behind Sir Robin.[2]
Details
Each individual metacell behaves as an 8-state, 4-neighborhood BCC-automaton; the metacell receives a glider-based signal (a positive integer between 1 and 7, inclusive) from each of its (up to four) neighbours, and a 0 from any empty spaces if there are fewer than four neighbours. It then computes the quantity 83 a + 82 b + 81 c + d, where (a, b, c, d) are the four input signals, and indexes into a 4096-element lookup table to retrieve a value between 0 and 7 (the new ‘state’ of the metacell). If 0, it immediately self-destructs without constructing any children; if nonzero, it constructs a daughter machine in each vacant space. Finally, it broadcasts the new state as a signal to all four neighbours, before self-destructing. In doing so, the metacell behaves as a single cell in any 8-state 4-neighbor cellular automaton; as every 2-state 9-neighbour cellular automaton can be emulated at half the speed as an 8-state 4-neighbour cellular automaton, this allows the 0E0P metacell to emulate rules other than Life, which also allows it to act as a parity-rule replicator, a reflectorless rotating oscillator (with some limits), and a SMOS if programmed correctly.
In a healthy 0E0P metacell pattern, metacells could be thought of as living on a diagonally-oriented checkerboard. They're allowed to be present on the dark squares of the checkerboard only during even 235-tick half-cycles, and on the light squares of the checkerboard only during odd half-cycles. At the beginning of each even half-cycle, or in other words at the beginning of each full metatick, the presence or absence of an 0E0P metacell on a dark square corresponds with the presence or absence of an ON cell in an equivalent Life grid (assuming the metacell is programmed to emulate B3/S23). At other times during the 0E0P's replication cycle, the correspondence with cells on a Life grid won't be as clean, but every 236 ticks the 0E0P metapattern will come back into perfect alignment.
Every period-236 cycle of an 0E0P metacell consists of two period-235 half-cycles. In each half-cycle, all metacells make sure that there are child metacells all around them, on the other checkerboard square color -- either by building them, or by attempting to build them and having the construction recipe cleanly eaten by an eater that's part of an already existing child in that location.
Notice that with the 45-degree checkerboard orientation, each grid location in the emulated Life pattern is only half filled by a 0E0P metacell (if one is present). In other words, the metacells are diamond-shaped, not square; their sides don't line up with the emulated Life grid.
Switching checkerboard colors and expanding to four surrounding metacells twice (for two half-cycles) effectively ensures that all eight metacells surrounding any given ON metacell on the same checkerboard square color are occupied by child metacells. These are all the neighbor locations for that particular metacell. No effect can travel faster than lightspeed in the range-1 Moore-neighborhood rules that the 0E0P metacell can emulate, so at the end of two half-cycles, metacells are present in every location where a metacell could possibly be needed to turn ON in the next metatick.
There's no direct communication between an 0E0P metacell and its nearest possible living neighbor metacells to the north, south, east, and west -- i.e., the nearest same-color squares on the 45-degree-angled checkerboard -- let alone between it and the other possibly-living neighbor cells, two checkerboard squares away diagonally. However, by the end of each full cycle, communication between parent and child metacells during each half-cycle has effectively transmitted neighbor state information from one dark-square metacell to all its dark-square neighbors. This means that at the end of each half-cycle, every "potentially alive" 0E0P metacell has all the information it needs to decide whether it should transition to a "fully alive" state and start building child metacells, or if it should immediately self-destruct instead.
LifeViewer demo
To demonstrate the full 0E0P metacell cycle and the early self-destruct option, the LifeViewer demo below shows how a glider made of metacells proceeds through a full 236 period (or "metatick"). Note that the gap between metacells where the equivalent cells would be diagonally adjacent will not be visible at the proper zoom level.
Complexity
The metacell's circuitry is sufficiently complex that a single Conway's Life meta-glider requires a compressed pattern file several megabytes in size.[3] It can be run in Golly at small step sizes with no difficulty, but simulating an entire replication cycle (half a metatick) is very difficult. On current computers it might take about half a CPU-year using Golly's standard HashLife algorithm.
An order of magnitude improvement over HashLife is available via Goucher's special-purpose StreamLife algorithm. However, even using StreamLife it might take several months to simulate the eight replication cycles (four full metaticks) needed to return a metaglider to its original phase. The original experimental verification of a single metatick (12:05 to 12:35 in Cabaret's video below), using rule where a single ON cell is a still life, took about a month.
Videos
References
- ↑ "Fully Self-Directed Replication". Adam P. Goucher (November 12, 2018). Retrieved on January 8, 2019.
- ↑ Oscar Cunningham (January 23, 2019). Re: Pattern of the Year 2018 competition: Voting (discussion thread) at the ConwayLife.com forums
- ↑ Dave Greene (November 8, 2018). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums