Tutorials/General technology

Tutorials/General technology

So now, after coming across a good cellular automata, you have decided to do something less abstract with it — something more significant than random soup searching and more engaging than automatic software searching. Then you begin to consider signal circuitry, the very connection between microscopic evolution and macroscopic construction. (Actually, that is approximately what cellular automata were originally created for; the basis of modelling self-replicating systems.)

What is a signal and what do they do?

A signal is a moving configuration different from its background, and thus carrying some information from simple presence/absence to phase difference. In terms of cellular automata, the following patterns can serve as signals:

• Spaceships in an empty medium,
• Fuses, drifters and negative spaceships in some nonempty media, and
• Active reactions, particularly methuselahs, in conduits.

A signal travels through the space at a certain speed, which is an important measure since timing (especially synchronization) decides whether signal circuitry works or not.

Signals transform and interact in various ways. A lone signal can be created, reflected and/or flipped, delayed/advanced, multiplicated, transformed into other signal(s), or destroyed. Two or more signals can be synchronized, or subject to reactions that annihilate or perform logic operations. These rely on some devices, namely guns/factorys, reflectors, advancer, pulse dividers, fanouts, converters, eaters, Boolean logic gates, etc.

Note that signal circuitry in cellular automata is very different from that with other physical implementations. For instance, there is no law of mass conservation (population count is not fixed for many CAs) nor notion of potential difference in a force field.

How to find these building blocks?

This page is under construction. Sorry for the inconvenience.

Constructing signal circuitry involves both human idea and computer power. Here some simple demonstration may provide hints on how to do that.

Example 1: Conway's Game of Life, with the Gosper glider gun

The signal: glider

Imagine travelling back to the early life days in the 1970s. When tracking the evolution of small polyomino patterns, Life enthusiasts observed a moving configuration as follows:

x=3, y = 3, rule = B3/S23 bo$2bo$3o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 AUTOSTART GPS 4 LOOP 4 TRACK 0.25 0.25 ]]

Soon the spaceship became known as the glider, and found its part in the signal circuitry. Let's analyze its movement.

A glider travels one cell down and one cell right in four ticks, during which it shows two alternating shapes in a glide-symmetric manner. To reflect these facts we have some terminologies:

Time-lapse visualization of glider-related concepts

• Phase: the arrangement of cells in one tick. A glider has 4 phases.
• Period: the minimum number of ticks passed to appear in the same phase. A glider is period 4.
• Speed: the displacement in a period divided by period. A glider has speed (1,1)c/4.
• Mod: because the 1st&3rd phase are identical considering reflection and translation, and so does the 2nd&4th, a glider is said to have a mod of 4/2 = 2.
• Lane: the diagonal linear region where a travelling glider has covered or will cover. Since it is diagonal, a new metric for the distance parallel and perpendicular to the direction is invented. Define one half-diagonal (1hd) as the length of one half diagonal line of the square cell, that is, the distance between the blue line and the red line on the right.

Additionally, we will need to define parity and color so as to describe the relationship between two gliders. Gliders in the 1st and 3rd phase (or 2nd and 4th, with pairwise identical shapes) are said to have the same parity. Gliders in the same phase up to rotation but no reflection are considered to have the same color if their corresponding cell coordinates have even sum (or odd sum).

The signal sink: eater 1

An important question following the discovery of glider is, what can we use when we want to suppress a glider? A number of collisions between a glider and some simple patterns have been tested. Fortunately, the following 7-cell fishhook-shaped still life can kill a glider and then recover in four ticks.

x=9, y = 9, rule = B3/S23 bo$2bo$3o3$5b2o$5bobo$7bo$7b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 AUTOSTART GPS 4 LOOP 12 ]]

This is called an eater, a subgroup of catalysts. It is reusable, and it allows for gliders to be eaten at any time without adjusting phases.

The signal source: Gosper glider gun

Since the discovery of glider, people have been seeking for patterns that generates gliders. Later, a sustainable collision between two queen bees was discovered that could yield gliders again and again. This is known as the period-30 Gosper glider gun:

x=41, y = 27, rule = B3/S23 24bo$22bobo$12b2o6b2o$11bo3bo4b2o12b2o$10bo5bo3b2o12b2o$2o8bo3bob2o4bo bo$2o8bo5bo7bo$11bo3bo$12b2o$23bo$24b2o$23b2o6$30bobo$31b2o$31bo5$38bo $39b2o$38b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 AUTOSTART GPS 8 LOOP 30 ZOOM 8 ]]

Generally, a signal device may take a number of inputs and yield some outputs. When there are more outputs than inputs, it is said to be an over-unity reaction. With assistance, this kind of reactions are useful for constructing signal emitters. Taking no inputs and giving outputs periodically, the Gosper glider gun can be considered a degenerate example of over-unity reaction.

In the following sections, we will not discuss about the inner workings of the Gosper glider gun, instead it will be used as a whole.

Signal interactions: glider collisions

Next, we want to know how gliders can react with each other. Beginning with the simplest case of two gliders, we enumerated two-glider collisions. Of particular interest are the cases where two glider destroy each other completely:

x=325, y = 35, rule = B3/S23 100bo36bo18bo$4bo18bo19bo16bo19bo18bo19bo16bo18bo36bo$3bo18bo19bo16bo 19bo19b3o16bo17b3o16b3o15bo17bo$3b3o16b3o17b3o14b3o17b3o36b3o51bo18b3o $172b3o4$136bo$4b3o17b3o89bo18b2o55bo$4bo19bo20bo17bo20bo13b2o15b2o18b obo14b2o20bo16b2o$5bo19bo18b2o16b2o19b2o13bobo14bobo34bobo18b2o16bobo$ 44bobo15bobo18bobo12bo53bo20bobo7$261bo$215bo22bo21bo62bo$176bo15bo21b o22bo22b3o18bo22bo17bo$175bo15bo22b3o20b3o40bo22bo18b3o$32bo16bo17bo 16bo16bo15bo17bo16bo22b3o13b3o86b3o20b3o$12bo18bo16bo17bo16bo16bo15bo 17bo16bo$11bo19b3o14b3o15b3o14b3o14b3o13b3o15b3o14b3o$11b3o4$170b3o15b 3o59b2o$22b3o16b3o16b3o15b3o15b3o14b3o16b3o15b3o19bo17bo11b2o23b2o20bo bo20b2o40b2o$3o21bo18bo18bo17bo17bo16bo18bo17bo18bo17bo13b2o23b2o21bo 21b2o12b2o26b2o$2bo20bo18bo18bo17bo17bo16bo18bo17bo50bo24bo44bo15b2o 24bo$bo285bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 WIDTH 1400 HEIGHT 400 ZOOM 4 ]]

These annihilation reactions will be the basis of signal devices below.

Also we observe the cases with clean output glider:

x=29, y = 14, rule = B3/S23 7bo$6bo20bo$6b3o17bo$26b3o7$23bo$b2o19b2o$obo19bobo$2bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 ]]

Looking closer, they are actually kickback reactions in which one of the gliders is reflected 180 degrees, which is somewhat limited. It would be better if there were two-glider collisions in Game of Life that

• give the output on a lane perpendicular to both of the inputs,
• kill one of the inputs while keeping the other unaffected, as in a Heisenburp-type fly-by reaction, or
• are clean unity or over-unity reactions themselves.

Signal reflectors

Signals don't turn around themselves, so reflectors are needed to adjust their orientation. Generally, a signal reflector takes one input signal and gives one output in a different direction.

With two Gosper glider guns, a period-30 glider reflector can be constructed. The plan is

• When there is no glider input, the two guns should not emit any glider at all.
• When a third glider comes in, it suppresses one of the two gliders above, leaving another one escape.

Take the first 90-degree annihilation reaction above, and we can construct the following period-30 oscillator with guns in-phase:

x=37, y = 43, rule = B3/S23 11bo$11bobo$14b2o6b2o$2o12b2o4bo3bo$2o12b2o3bo5bo$11bobo4b2obo3bo8b2o$ 11bo7bo5bo8b2o$20bo3bo$22b2o$12bo$10b2o$11b2o6$3bobo$3b2o$4bo4$5bo$4b 2o$4bobo6$12b2o$11b2o$13bo$23b2o$21bo3bo$12bo7bo5bo8b2o$12bobo4b2obo3b o8b2o$b2o12b2o3bo5bo$b2o12b2o4bo3bo$15b2o6b2o$12bobo$12bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 400 WIDTH 600 GPS 8 LOOP 30 ]]

Drop in a third glider so that it destroys one of the gun outputs:

x=45, y = 43, rule = B3/S23 19bo$19bobo$22b2o6b2o$8b2o12b2o4bo3bo$8b2o12b2o3bo5bo$19bobo4b2obo3bo 8b2o$19bo7bo5bo8b2o$28bo3bo$30b2o$20bo$o17b2o$b2o16b2o$2o5$11bobo$11b 2o$12bo4$13bo$12b2o$12bobo6$20b2o$19b2o$21bo$31b2o$29bo3bo$20bo7bo5bo 8b2o$20bobo4b2obo3bo8b2o$9b2o12b2o3bo5bo$9b2o12b2o4bo3bo$23b2o6b2o$20b obo$20bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 400 WIDTH 600 ]]

That's it, a working 180-degree glider reflector! But with 180-degree reflectors only we cannot get a glider to wherever it needs to be. We will then look for a 90-degree reflector. Relocate the glider so that it destroys a gun output head-on rather than at right angles, which leads to the following:

x=43, y = 43, rule = B3/S23 17bo$17bobo$20b2o6b2o$6b2o12b2o4bo3bo$6b2o12b2o3bo5bo$17bobo4b2obo3bo 8b2o$17bo7bo5bo8b2o$26bo3bo$28b2o$18bo$16b2o$17b2o6$o8bobo$b2o6b2o$2o 8bo4$11bo$10b2o$10bobo6$18b2o$17b2o$19bo$29b2o$27bo3bo$18bo7bo5bo8b2o$ 18bobo4b2obo3bo8b2o$7b2o12b2o3bo5bo$7b2o12b2o4bo3bo$21b2o6b2o$18bobo$ 18bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 400 WIDTH 600 ]]

Example 2: Banks-I

Also see: Introduction to Banks-I

Banks-I is an isotropic non-totalistic Life-like cellular automaton for which investigation began in the infant of Game of Life.

Prerequisities: signal and its source & sink

A "wire" consists of a three-cell-thick block of live cells, and a "signal" is carried by a duoplet-shaped perturbation travelling at lightspeed along the edge of a wire. A five-cell bump extension and an additional cell on the edge can kill a signal.

x=52, y = 56, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 o18bo$5ob14o$4ob15o$20o6b5o2b5o2b5o2b5o$o18bo7b3o4b3o4b3o4b3o$27b3o4b 3o4b3o4b3o$27b3o4b3o4b3o4b3o$o18bo7b3o4bobo4b3o4bobo$15ob4o7b3o5b2o4b 3o4b2o$16ob3o7b3o4b3o4b3o4b3o$20o7b3o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b 3o$27b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o7b3o4b 3o4b3o4b3o$4ob15o7b3o4b3o4b3o4b3o$5ob14o7b3o4b3o4b3o4b3o$o18bo7b3o4b3o 4b2o5b3o$28b2o4b3o4bobo4b3o$27bobo4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$ 20o6b5o2b5o2b5o2b5o$17ob2o$16ob3o$o18bo5$o13bo4bo$5ob14o$4ob15o$20o6b 5o2b5o2b5o2b5o$o18bo7b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b 3o$o6bo11bo7b3o4bobo4b3o4bobo$15ob4o7b3o5b2o4b4o3b2o$16ob3o7b3o4b3o4b 3o4b3o$20o6b4o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$27b3o4b3o4b3o4b3o$27b 3o4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o7b3o4b3o4b3o4b3o$4ob15o7b3o3b 4o4b3o4b4o$5ob14o7b3o4b3o4b3o4b3o$o12bo5bo7b3o4b3o4b2o5b3o$28b2o4b3o4b obo4b3o$27bobo4b3o4b3o4b3o$o18bo7b3o4b3o4b3o4b3o$20o6b5o2b5o2b5o2b5o$ 17ob2o$16ob3o$o5bo12bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 WIDTH 600 HEIGHT 600 ]]

Signals can be emitted at regular intervals with a "clock". These devices are essentially period-2ⁿ signal factories driven by Rule 90 replicator loops.

x=30, y = 16, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 5bo11bo$5b13o$bo3b13o$b17o$3obo12bo$4bo5$9bo19bo$9b21o$bo7b21o$b29o$7o bo20bo$8bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 ]]

Example 3: B2a/S, with the replicator

B2a/S is also an isotropic non-totalistic Life-like cellular automaton, but with only one birth transition. It is characterized by the only moving configuration, the domino replicator, that messes up every random configuration:

x=1, y = 2, rule = B2a/S o$o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 AUTOSTART GPS 2 PAUSE 2 LOOP 33 T 32 PAUSE 2 ]]