0E0P metacell

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. 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 = 2¹⁸. 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.

The 0E0P metacell ranked second place in the Pattern of the Year 2018 competition on the ConwayLife.com forums, behind Sir Robin.

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, 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^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^36 ticks the 0E0P metapattern will come back into perfect alignment.

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.

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 2^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.

x=233, y = 233, rule = none 206.I$205.3I$204.5I$203.7I$202.3IEIE3I$201.3IEIEIE3I$200.5IEIEIE3I$ 201.5IEIE3I$202.3IEIE3I$203.3IE3I$204.5I$205.3I$206.I8$186.I39.I$185. 3I37.3I$184.5I35.5I$183.7I33.7I$182.3IDID3I31.9I$181.3IDIDID3I29.6IE 4I$180.5IDIDID3I27.8IE4I$181.5IDID3I29.4IEIE4I$182.3IDID3I31.6IE2I$ 183.3ID3I33.7I$184.5I35.5I$185.3I37.3I$186.I39.I8$166.I39.I$165.3I37. 3I$164.5I35.5I$163.7I33.2IHIH2I$162.3ICIC3I31.2IHIHIH2I$161.3ICICIC3I 29.2IHIHIDIH2I$160.5ICICIC3I27.4IHIHIDIH2I$161.5ICIC3I29.4IDIDIH2I$ 162.3ICIC3I31.2IHIHID2I$163.3IC3I33.2IHIH2I$164.5I35.2IH2I$165.3I37. 3I$166.I39.I8$146.I39.I$145.3I37.3I$144.5I35.5I$143.7I33.2ICIC2I$142. 3IBIB3I31.2ICICIC2I$141.3IBHBHB3I29.2ICICICIC2I$140.5IBIBHB3I27.4ICIC ICIC2I$141.5IBHB3I29.4ICICIC2I$142.3IBHB3I31.2ICICIC2I$143.3IB3I33.2I CIC2I$144.5I35.2IC2I$145.3I37.3I$146.I39.I8$126.I39.I$125.3I37.3I$ 124.5I35.5I$123.7I33.2IBIB2I$122.3IAIA3I31.2IBHBHB2I$121.3IAGAGA3I29. 2IBHBHBHB2I$120.5IAIAGA3I27.4IBHBHBHB2I$121.5IAGA3I29.4IBHBHB2I$122. 3IAGA3I31.2IBHBHB2I$123.3IA3I33.2IBHB2I$124.5I35.2IB2I$125.3I37.3I$ 126.I39.I8$106.I39.I$105.3I37.3I$104.5I35.5I$103.7I33.2IAIA2I$102.3IA IA3I31.2IAGAGA2I$101.3IAFAFA3I29.2IAGAGAGA2I$100.5IAIAFA3I27.4IAGAGAG A2I$101.5IAFA3I29.4IAGAGA2I$102.3IAFA3I31.2IAGAGA2I$103.3IA3I33.2IAGA 2I$104.5I35.2IA2I$105.3I37.3I$106.I39.I8$86.I39.I$85.3I37.3I$84.5I35. 5I$83.7I33.2IAIA2I$82.3IAIA3I31.2IAFAFA2I$81.3IAFAFA3I29.2IAFAFAFA2I$ 80.7IAFA3I27.4IAFAFAFA2I$81.5IAFA3I29.4IAFAFA2I$82.3IAFA3I31.2IAFAFA 2I$83.7I33.2IAFA2I$84.5I35.2IA2I$85.3I37.3I$86.I39.I8$66.I39.I$65.3I 37.3I$64.5I35.5I$63.7I33.2IAIA2I$62.3IAIA3I31.2IAFAFA2I$61.4IFAFA3I 29.2IAFAFAFA2I$60.7IAFA3I27.4IAFAFAFA2I$61.5IAFA3I29.4IAFAFA2I$62.4IF A3I31.2IAFAFA2I$63.7I33.2IAFA2I$64.5I35.5I$65.3I37.3I$66.I39.I8$46.I 39.I$45.3I37.3I$44.5I35.5I$43.7I33.2IAIA2I$42.9I31.2IAFAFA2I$41.4IFAF A3I29.3IFAFAFA2I$40.8IFA3I27.5IFAFAFA2I$41.6IFA3I29.4IAFAFA2I$42.4IFA 3I31.3IFAFA2I$43.7I33.3IFA2I$44.5I35.5I$45.3I37.3I$46.I39.I8$26.I39.I $25.3I37.3I$24.5I35.5I$23.7I33.7I$22.9I31.3IFAFA2I$21.4IFIF4I29.3IFAF AFA2I$20.8IF4I27.5IFAFAFA2I$21.6IF4I29.5IFAFA2I$22.4IF4I31.3IFAFA2I$ 23.7I33.3IFA2I$24.5I35.5I$25.3I37.3I$26.I39.I8$6.I39.I$5.3I37.3I$4.5I 35.5I$3.7I33.7I$2.9I31.3IFIF3I$.4IEIE4I29.3IFIFIF3I$8IE4I27.5IFIFIF3I $.6IE4I29.5IFIF3I$2.4IE4I31.3IFIF3I$3.7I33.3IF3I$4.5I35.5I$5.3I37.3I$ 6.I39.I8$26.I$25.3I$24.5I$23.7I$22.3IEIE3I$21.3IEIEIE3I$20.5IEIEIE3I$ 21.5IEIE3I$22.3IEIE3I$23.3IE3I$24.5I$25.3I$26.I! #C [[ COLOR 1 Yellow COLOR 2 Orange COLOR 3 Pink COLOR 4 Gray COLOR 5 Purple ]] #C [[ COLOR 6 Blue COLOR 7 Cyan COLOR 8 Red COLOR 9 Green ]] #C [[ LABELSIZE 12 LABELALPHA 1 LABELANGLE 315 COLOR LABEL White ]] #C [[ GRID ANGLE 45 HEIGHT 600 THEME MCell GRIDMAJOR 0 ]] #C [[ POI X -108 Y 92 Z 32 POITRANS 0 ]] Point of interest #1 #C [[ LABEL 11 211 16 "Here's where it all starts\n-- five metacells forming a glider, in Stage E\n(shown in purple)" ]] #C [[ POI X -88 Y 72 Z 32 POITRANS 0 ]] POI #2 #C [[ LABEL 31 191 16 "Metacells move to Stage F (blue).\n-- ready to start constructing children, SE first" ]] #C [[ POI X -68 Y 52 Z 32 POITRANS 0 ]] POI #3 #C [[ LABEL 51 171 16 "Metacells remain in Stage F (blue).\nChildren constructed SE of each metacell\n(yellow cells, Stage A)" ]] #C [[ POI X -48 Y 32 Z 32 POITRANS 0 ]] POI #4 #C [[ LABEL 71 151 16 "Metacells remain in Stage F (blue).\nChildren constructed NE of each metacell\n(yellow cells, Stage A)" ]] #C [[ POI X -28 Y 12 Z 32 POITRANS 0 ]] POI #5 #C [[ LABEL 91 131 16 "Metacells remain in Stage F (blue).\nChildren constructed NW of each metacell\n(yellow cells, Stage A)" ]] #C [[ POI X -8 Y -8 Z 32 POITRANS 0 ]] POI #6 #C [[ LABEL 111 111 16 "Metacells remain in Stage F (blue).\nChildren constructed SW of each metacell\n(yellow cells, Stage A)" ]] #C [[ POI X 12 Y -28 Z 32 POITRANS 0 ]] POI #7 #C [[ LABEL 130 90 16 "Original metacells move to Stage G (cyan).\nParent metacells send their own states\nto each immediate neighbor. All receiving neighbors\nare recently constructed child metacells." ]] #C [[ POI X 32 Y -48 Z 32 POITRANS 0 ]] POI #8 #C [[ LABEL 150 70 16 "Metacells move to Stage H (red)\nThe cycle is complete. The original metacells self-destruct.\nState signals from the original metacells are collected and\nstored in registers in each neighboring child cell,\nwhich have all now moved to Stage B (orange)" ]] #C [[ POI X 52 Y -68 Z 32 POITRANS 0 ]] POI #9 #C [[ LABEL 170 50 16 "Original metacells are gone now\n(green is the background state, completely empty).\nThe four child metacells move to Stage C (pink)\nIn each metacell, the collected state values from each\nneighbor are used to calculate the future state of the cell." ]] #C [[ POI X 72 Y -88 Z 32 POITRANS 0 ]] POI #10 #C [[ LABEL 190 30 16 "The child metacells move to Stage D (gray)\nIf a child metacell's new calculated state is 0, it\nself-destructs. Here all 13 child metacells survive.\nThis is what always happens in the first\nhalf-cycle, when a Moore-neighborhood rule\nis being emulated." ]] #C [[ POI X 92 Y -108 Z 32 POITRANS 0 ]] POI #11 #C [[ LABEL 211 11 16 "The thirteen child metacells move to Stage E (purple)\nThe construction/signal/collect/decide cycle begins again.\nThis cycle happens twice in each 2^36 0E0P metacell cycle." ]] #C [[ POI X -88 Y 112 Z 32 POITRANS 0 ]] POI #12 #C [[ LABEL 30 230 16 "The cycle restarts.\nNow there are thirteen metacells, all in Stage E\n(shown in purple)" ]] #C [[ POI X -68 Y 92 Z 32 POITRANS 0 ]] POI #13 #C [[ LABEL 50 210 16 "The thirteen metacells move to Stage F (blue)\n-- ready to start constructing children, SE first" ]] #C [[ POI X -48 Y 72 Z 32 POITRANS 0 ]] POI #14 #C [[ LABEL 70 190 16 "The thirteen metacells remain in Stage F (blue).\nThirteen children are constructed in the SE\n(yellow metacells, Stage A)" ]] #C [[ POI X -28 Y 52 Z 32 POITRANS 0 ]] POI #15 #C [[ LABEL 90 170 16 "The thirteen metacells remain in Stage F (blue).\nFour more children are constructed in the NE\n(yellow metacells, Stage A)" ]] #C [[ POI X -8 Y 32 Z 32 POITRANS 0 ]] POI #16 #C [[ LABEL 110 150 16 "The thirteen metacells remain in Stage F (blue).\nFour more children are constructed in the NW\n(yellow metacells, Stage A)" ]] #C [[ POI X 12 Y 12 Z 32 POITRANS 0 ]] POI #17 #C [[ LABEL 130 130 16 "The thirteen metacells remain in Stage F (blue).\nOne more child is constructed in the SW\n(yellow metacell, Stage A)" ]] #C [[ POI X 32 Y -8 Z 32 POITRANS 0 ]] POI #18 #C [[ LABEL 150 110 16 "Metacells move to Stage G (cyan).\nEach parent metacell sends its own state to each neighbor." ]] #C [[ POI X 52 Y -28 Z 32 POITRANS 0 ]] POI #19 #C [[ LABEL 170 90 16 "Parent metacells move to Stage H (red).\nChild metacells move to stage B (orange).\nThe parent metacells self-destruct, as always.\nState signals from the parent cell are stored in registers\nin the new child cells." ]] #C [[ POI X 72 Y -48 Z 32 POITRANS 0 ]] POI #20 #C [[ LABEL 190 70 16 "The thirteen parent metacells are gone now -- back to the\ngreen background state, completely empty.\nThe twenty-two child metacells move to Stage C (pink)\nIn each metacell, the collected neighbor states\nare used to calculate the future state of the metacell." ]] #C [[ POI X 92 Y -68 Z 32 POITRANS 0 ]] POI #21 #C [[ LABEL 210 50 16 "The twenty-two child metacells move to Stage D (gray)\nIf a child metacell's calculated state is 0, it self-destructs.\nIn this case, where a B3/S23 glider is being emulated,\nonly five of the twenty-two child metacells survive." ]] #C [[ POI X 112 Y -88 Z 32 POITRANS 0 ]] POI #22 #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 [[ 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. 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

Click to load content

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