# 0E0P metacell

0E0P metacell
Pattern type Unit cell
Number of cells ~ 18650000
Bounding box 261841×261841
Cell size 262144×262144
Period 68719476736
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.

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

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