Difference between revisions of "0E0P metacell"
(Taken from Dave Greene's explanation on the forums and Goucher's explanation on the linked blog post. Correct me if any of this is mistaken.) |
|||
Line 20: | Line 20: | ||
==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^3 a + 8^2 b + 8^1 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. | |||
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 on even metaticks, and on the light squares of the checkerboard only on even ticks. Every period-2^36 cycle of an 0E0P metacell consists of two period-2^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. 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 full 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 self-destruct. | |||
To demonstrate this, the LifeViewer demo shown below shows how a glider made of metacells proceeds through a full 2^36 period (or "metatick"). | |||
{{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 107: | Line 111: | ||
#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' to move forward through 0E0P stages,\nor 'Shift+J' to move backwards." ]]}} | #C [[ LABEL 245 6 16 "Press 'J' to move forward through 0E0P stages,\nor 'Shift+J' to move backwards." ]]}} | ||
==Videos== | ==Videos== |
Revision as of 04:09, 23 June 2019
This article is a stub. You can help LifeWiki by expanding it. |
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" was originally 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^36 times more slowly, and if they're run at a step size lower than 2^36, intermediate states may be visible that will depart from a strict pixel-for-pixel match.
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^3 a + 8^2 b + 8^1 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.
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 on even metaticks, and on the light squares of the checkerboard only on even ticks. Every period-2^36 cycle of an 0E0P metacell consists of two period-2^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. 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 full 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 self-destruct.
To demonstrate this, the LifeViewer demo shown below shows how a glider made of metacells proceeds through a full 2^36 period (or "metatick").
Videos
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.[2] 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), using rule where a single ON cell is a still life, took about a month.
References
- ↑ "Fully Self-Directed Replication". Adam P. Goucher (November 12, 2018). Retrieved on January 8, 2019.
- ↑ Dave Greene (November 8, 2018). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums