Intro: OTCA Metapixel - Conway's Game of Life
Conway's Game of Life is a type of 2D cellular automaton that uses a simple set of rules to describe the behavior of cells over discrete time steps. Surprisingly, you can generate very complex behavior from cellular automata even though the rules can usually be summed up in a sentence. In 2D cellular automata, a cell's behavior in the next time step is dictated by its current state and the current state of its eight neighbors. The rules for Conway's game of life are reproduced below:
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by overcrowding.
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Many interesting patterns have been studied in Life, a few simple patterns are shown here. Some patterns, called "still lifes" are stationary and do not change over time (block, loaf, boat) . "Oscillators" are pattern that repeat themselves after a certain number of time steps (blinker, beacon, pulsar). "Spaceships" are a type of oscillator that move across space as they oscillate. The simplest and most common form of spaceship is called a glider. Another common spaceship is the light weight spaceship. "Guns" are structures that produce a stream of spaceships, here's is an example of Gosper's glider gun. Some very simple initial conditions create complex behavior, as is the case with the r pentomino, a five cell pattern.
Using a combination of spaceships, still lifes, oscillators, guns, and other basic objects, it's possible to construct incredibly complex structures in Life. Here's an example of a period 416 gun that constructs 60P5H2V0 spaceships using a series of timed glider collisions:
In 2006 Brice Due published a structure called the OTCA Metapixel; its purpose is to emulate the behavior of a single Life cell. I came across this video last week and decided I had to figure out how it works:
The OTCA Metapixel isn't the first or the fastest metapixel discovered in Life (also check out the P5760 unit Life cell and the Deep cell), but it has the interesting property of looking like a life cell when zoomed out. It also has a register that allows you to program it to behave according to any arbitrary Life-like cellular automaton ruleset.
Here's how it works:
Clock - A tractor beam is a stream of spaceships that slowly pull an object towards the direction of its source. A simple example is the loaf tractor beam. This video shows a slightly different type of tractor beam in a sawtooth.
The OTCA Metapixel uses a tractor beam as a clock to regulate the timing of events:
In the video above, a tractor beam pulls a block down by 8 cells in each collision, releasing a glider to the right each time. A fence to the side of the tractor beam made of Eater 1's destroys the gliders immediately, but there are a few holes in the fence that allow gliders to pass through and interact with other structures in the metapixel at regularly timed intervals.
The first shot in the video shows the source of the block and three gliders firing into a light-weight space ship (LWSS) packet gun, which then shoots out three sets of three LWSSes, one set for each incoming glider. The next shot shows the source of the tractor beam and four more gliders fired from the tractor beam into the metapixel. This first glider initiates a neighbor count decode sequence, the next two gliders read the results from the decoder, and the last glider initiates a logic cascade that eventually decides whether to turn the metapixel on or off in the next clock cycle (all described in more detail later). The role of the 7 gliders is summed up in this image.
During each cycle of the OTCA Metapixel clock, the block is destroyed at the source of the tractor beam and restored in its starting position, continuing the cycle.
Rules and Logic - The rules of the metapixel are encoded in two columns (registers) as shown in the images below. Life-like automata rules are written in the form B#/S#, described here. Conway's rules are defined as B3/S23, so the corresponding bits of the registers of the OTCA metapixel are populated with one Eater-1 each.
On each clock cycle three sets of three LWSSes (9 total in a single line) are shot out from a packet gun (triggered by the clock, explained above) and sent out on a complete loop around the metapixel. As the train of spaceships pass by each of its Moore neighbors the first ship in the train will collide with a pond in its path if the neighbor is currently alive, destroying the ship and decreasing the total number of ships in the train by one. So if a metapixel has 4 alive neighbors, only five LWSSes will return after completing a pass around the perimeter. A collision of a train of LWSSes with a pond is shown below at about 0:32 (I'll explain how the ponds get there later):
This video also shows the shepherding of the train of LWSSes around the metapixel by twin bees shuttles and other reflectors, and an example of "color adjustment" of the ships (changing their phase slightly) by a pair of glider guns. The path of the LWSSes along with the location of color adjusters and possible ponds is shown in this image.
The full path of the LWSS train is shown below. Notice how one ship is removed from the front of the train as it passes each living neighbor.
When the train of LWSSes completes a loop, they are channeled into a sync buffer and p46 to p40 converter where they given the same phase. Then they are sent into the rules register where they are collided with another LWSS coming from the opposite direction (originating from one of the gliders shot out of the clock) to decode the train of LWSS into the number of living neighbors (shown in this diagram).
The location of the collision between the LWSS train and the LWSS originating form the clock depends on how many LWSS were destroyed from the front of the train during the loop around the metapixel. The mechanism is set up so that the collision shoots out two gliders in opposite directions, aimed towards the register that corresponds to the number of living neighbors the metapixel has (again, see this pic as a reference).
Normally, the gliders will each collide with a beehive to produce a block and a pond, this is called a honeybit reaction. If you watch from about 6 min into the video above, you'll see the collision of the antiparallel LWSSes, sending two gliders towards 4th slot (count up from the bottom, starting at 0) in both the birth and survival registers, and at about 6:30 two ponds are formed in the registers. The remaining spaceships in the LWSS train collide with an Eater-1 and are destroyed. The video below shows a closer look across many generations:
If the slot in the register is occupied by an Eater-1 (as are the 3rd slot in the birth register, and the 2nd and 3rd slots in the survival registers, again counting up from the bottom starting at 0), then the incoming glider is destroyed before it has a chance to intiate a honeybit reaction with the beehive. This produces no pond in the register. In this mechanism a register has a pond if the number of living neighbors doesn't satisfy the conditions for life in the next generation, and no pond if it does. Remember this information is split between two registers (birth and survival) and in a later step some logic will look at the current state of the metapixel to determine which register to read from (described later). This mechanism is what makes the OTCA Metapixel programmable for any Life-like ruleset, pretty cool.
Next, the clock shoots out a pair of LWSSes to read these registers (one LWSS for each register), following the trajectories shown in this diagram. If a pond is present in a register, the LWSS collides with the pond and is destroyed. This completes the honeybit reaction and restores the beehive in the same position it was originally. If the LWSS has no pond in its path, it is allowed to continue into the next logic mechanism. In the video above, see if you can predict the next state of the metapixel by reading from the registers.
Before I move to the final logic of the system, I'll look at how the neighbors' states are tallied up. This diagram shows the 8 input/ouput channels of each metapixel. By taking a closer look at one of them, you'll see another honeybit reaction happening:
The honeybit reaction on the left corresponds to the state of the metapixel on the right, and the reaction on the right corresponds to the state of the metapixel on the left. The LWSS train moves clockwise around the metapixel, so the train moving down the screen belongs to the pixel on the left and the train moving up the screen belongs to the pixel on the right.
These honeybit reactions are set by a middle weight spaceship (MWSS) that moves in a counter-clockwise path around the pixel each clock cycle. Here is a description of its path and the path of all the gliders it generates for 8 honeybit reactions around the metapixel. The MWSS is created only if the current state of the metapixel is alive and at the end of its loop around the pixel it is destroyed.
The final logic of the metacell is summarized in this diagram.
First some definitions:
C is the current state of the cell, 1 or 0
B is the state of the birth register, 1 for satisfied birth conditions, 0 for not-satisfied
S if the state of the survival register, 1 for satisfied, 0 for not-satisfied
The states of C, B, and S are stored in the metapixel by the presence ("1") or absence ("0") of three boats. Boats have the interesting property that when they are hit with a glider they reflect a new glider with a trajectory that is perpendicular to the path of the incoming glider. This collision destroys the boat, so boats are known as one time reflectors. The position of the boats in the metacell is shown in this diagram. The B and S boats are set using the LWSSes that are able to pass through the birth and survival registers during the decoding step described above. In this video, watch how the states of the B and S are set to "1" by a pair of LWSSes starting at 3:47, the moment they are set comes at 4:54:
A glider is used to read the states of C, B, and S and set a pond at G or H (shown in this diagram). The logic for G and H pond formation ("1" means a pond is formed, "0" means no pond) is given by the following logic:
If C is present, then:
G = !S (G equals the opposite of S)
H = 0
if C is not present:
G = 0
H = B
The final glider released by the clock (described at the beginning) sets of a logic cascade that computes these relationships. The glider is released through the small hole in the fence next to the clock, a little less than halfway up the left side of the video above, triggering the formation of a LWSS which travels toward the right side of the video, releasing two gliders on its way (example starting at about 16:12). The first glider bounces around and eventually turns into a LWSS that reads the results on G and H, more on that in the next paragraph. The second glider heads towards C, if C is present it reflects and starts heading toward S. If S is present it reflects into an eater and dies, if S is not present it continues to a beehive at G and does a honeybit reaction, forming a pond. If C is not present, the second glider heads toward B instead. If B is present, the glider reflects off B and does a honeybit reaction at H, otherwise it runs into an eater and dies. 16:20 in the video above shows the glider reflecting off C, passing through an absent S and forming a pond at G.
At 16:38 you can see a pond set at G and a LWSS coming in from the left to read G and H. If either G or H has a pond set, the LWSS is destroyed, as shown at 16:39. If neither are set (see 10:47) the LWSS continues on and forms a boat at notT (shown as T with a line on top on this diagram). This can be summarized with the logic:
notT = !(G || H) (notT equals 1 when G and H are both 0, otherwise it is 0)
A third glider released at 10:57 by the original LWSS logic cascade trigger heads toward notT. If the boat is present it reflects off the boat and hits an eater, if the boat is not present it continues to T (again, this diagram). The glider is destroyed by an eater in 11:16, but you can see it head to T starting at 5:33.
A fourth glider is released by the original LWSS which turns into a LWSS that cleans up any leftover boats left at B or S after the logical operations have completed. An example starts at 5:24. This LWSS has no other function, it is destroyed either by a boat it cleans up, or an eater. Its trajectory is shown here.
After all this we're left with the following state:
T = presence of a LWSS at T, the formal logic for this state is given by:
T = !notT = G || H = (C && !S) || (!C && B)
which you can read as "if the pixel is currently alive and it doesn't satisfy the requirements for survival, or if the pixel is currently dead and does satisfy the requirements for birth", basically if the next metapixel state is different from the current state there will be a LWSS at T.
The LWSS at T follows the path shown here. At 6:28 you can see an example of the LWSS turning into a series of twists and turns. At 6:39 it shoots a glider off which turns into an LWSS that heads to the sync buffer and eventually the cell state boat bit (different than C, more on this in the next paragraph). The original LWSS continues to the left, shooting another glider off at 6:44, creating a third LWSS which heads to the bottom right corner of the metapixel to toggle the state of the output display; the original LWSS heads to the top left corner of the metapixel to do the same (more on that in the next section).
The cell state boat bit is what actually stores the current state of the cell, (C is updated periodically based on the state of the boat bit). If the boat bit is present, indicating that the current state of the metapixel is "off", the incoming LWSS will form a glider that collides with it and removes it (starts at 7:03). If the cell state boat bit is not present, indicating that the current state of the metapixel is "on", the incoming LWSS will form a glider that creates a new boat bit (starts at 18:58).
Finally, let's follow the path of the original LWSS that triggered this whole series of events. It follows the outer path shown here, gets converted into a MWSS and heads towards the cell state boat bit. If the boat bit is present it collides with it and dies, though it does preserve the boat bit during this death (3:18). If the boat bit is not present it passes by unharmed and keeps heading to the right (7:14). This is the same MWSS that does a counterclockwise loop around the cell, triggering honeybit reactions on all the neighbors' inputs. This MWSS is only allowed to do the loop when the cell state boat bit is not present, when the metapixel is "on". Just before it leaves to do the loop it shoots off a glider that bounces around and eventually sets a boat at C (7:20). At 7:54 you can see it setting off the first of 8 honeybit reactions around the metapixel, one for each Moore neighbor.
Output Display - The last piece of the metapixel is the output display that uses a ton of spaceships to fill in a big square area so it looks more or less white. Two synchronized LWSSes toggle the output display; they came from the last logic mechanism described in the previous paragraphs, shown here. Their timing is synced up through a series of bends in their path and glider transformations, then they are used to toggle enable a HWSS gun that triggers a series of LWSS "out of the blue" reactions. The streams of LWSSes fill the square space and mutually annihilate each other in the center of the metapixel, shown here. The mechanisms for both latches are similar:
I've attached all the video files for this instructable below in case the compression from youtube is making them hard to see.