Difference between revisions of "0E0P metacell"

From LifeWiki
Jump to navigation Jump to search
(→‎Details: make more paragraphs, fix a few details)
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.  
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.  


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

Revision as of 14:43, 29 June 2019

Radiation.png This article is a stub. You can help LifeWiki by expanding it.
0E0P metacell
0E0P metacell 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, which also allows it to act as a parity-rule [[replicator], a reflectorless rotating oscillator (with some limits), and a SMOS if programmed correctly.

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.

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 the equivalent Life grid being emulated. 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.

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 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 immediately self-destruct instead.

To demonstrate this, the LifeViewer demo shown below shows how a glider made of metacells proceeds through a full 2^36 period (or "metatick").

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' to move forward through 0E0P stages,\nor 'Shift+J' to move backwards." ]]

Videos

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

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

  1. "Fully Self-Directed Replication". Adam P. Goucher (November 12, 2018). Retrieved on January 8, 2019.
  2. Dave Greene (November 8, 2018). Re: Thread for basic questions (discussion thread) at the ConwayLife.com forums