p1 megacell

From LifeWiki
Jump to: navigation, search
p1 megacell
p1 megacell image
Pattern type Unit cell
Number of cells 205145
Bounding box 32770×32770
Cell size 32768×32768
Period 16777216
Discovered by Adam P. Goucher
Year of discovery 2008

The p1 megacell is a unit cell capable of simulating any rule using the standard eight cell neighborhood, including non-totalistic rules — either isotropic non-totalistic (birth/survival conditions are based on the relative positions of neighbor cells, but the behavior of a given pattern is the same regardless of orientation) or anisotropic non-totalistic (behavior of some patterns changes under rotation and/or reflection).

The megacell is constructed almost entirely of stable circuitry, the only exception being the p16777216 gun that provides timing signals.

The cell, instead of being positioned with edges orthogonal, is rotated by 45°. This allows much of its information to be relayed by diagonally-travelling gliders.

Rule lookup mechanism

The key to understanding the megacell's operation is the locations numbered "0" through "8" in the south corner. Directly below each large number is a cluster of three eaters, which may or may not have a boat in the middle of them. These three eaters are a "demultiplexer" component invented by Brice Due, used here to store one bit of information.

The bit of information is the presence (boat) or absence (no boat) of an ON neighbor, according to the following diagram:

Labels in megacell (N=0 through 8) showing positions of megacell neighbor states recorded at each position:

 2   1   0 
3 8 7
4 5 6

To match the actual locations of neighbors in the Life universe, and the cardinal/intercardinal directions given below, this diagram and the next one should be rotated 45 degrees clockwise.

Thus, at the end of each megatick, there will be a boat below the "0" label if and only if the megacell to the east is ON. There will be a boat below the "1" label if and only if the megacell to the northeast is ON, and similarly for the rest of the above diagram. There will be a boat below the "8" label if and only if the state of the megacell itself is ON.

The rest of the mechanisms around the "0" through "8" labels send a stream of 2N gliders, all on the same output path. So the "0" mechanism sends only one glider, the "1" mechanism sends two gliders, etc., up to the "8" mechanism sending 256 gliders:

Number of gliders sent if location N contains a boat (2N):

4 2 1
8 256 128
16 32 64

The lower part of the circuitry just makes sure that the length-2N-1 salvo doesn't start getting fired until the length-2N salvo has safely gone by.

On the southeast edge of the megacell there's a complex shotgun aimed at a single block, near the end of the chain of 512 eaters (damaged or whole) in the "rule lookup table". You can see the damaged gliders at T=0 if you reset a megafied pattern, but they self-destruct within a few ticks.

Each glider sent on the output path ultimately triggers a shotgun salvo that pulls that block to the southeast, in 12-cell increments, lining up with each lookup-table eater in turn. When the final clock signal is sent from the p224 gun (which is the tiny mostly vertical line just to the right of the "8" mechanism), a different salvo is sent instead of the usual pull-block-12-cells one. That final salvo produces a 90-degree glider at the current location of the shotgun-pulled block, while destroying the block (which then gets rebuilt at the zero position by a separate signal).

That 90-degree glider output tests the presence or absence of that particular eater, and if the eater is not present, the test glider crashes into another glider which would otherwise escape NW to tell the cell to turn ON. Thus, as the label near the lookup table says, an eater's presence corresponds to an ON value for the next megatick; an eater's absence means the megacell will be OFF.

Emulatable rulespace

Thanks to the magic of binary addition of powers of two, each possible pattern of neighbors corresponds with exactly one eater position in the 512-eater lookup table. For example, if a megacell is currently OFF and has no neighbors, no gliders will be sent to the shotgun and so the block won't be moved at all. The eater at the NW end of the lookup table therefore means "megacell OFF, all neighbors OFF".

255 more eaters to the southeast of that first eater also mean "megacell currently OFF", and each eater location corresponds to one possible arrangement of ON and OFF neighbors of a central OFF cell. Similarly, the SE half of the lookup table means "megacell currently ON" (because the bit at the "8" label gets converted into 256 gliders). The first of those 256 gliders means "megacell ON, all neighbors OFF", and the last eater, farthest to the SE, means "megacell ON, all neighbors ON".

This size of lookup table codes for a truly huge space of 2512 possible rules — not just isotropic rules where a pattern is guaranteed to behave the same when it is reflected or rotated, but also asymmetric rules like "Conway's Life except also turn ON if the only a single neighbor to the north is ON." In other words, the megacell can be programmed to emulate every possible two-state Moore-neighborhood outer-totalistic or non-totalistic CA rule.

This 2512-sized non-totalistic rule space is natively supported by LifeViewer Build 222 and later and Golly 2.9 and later, in the form of the MAP rule syntax.

External links