Tutorials/General technology

From LifeWiki
Jump to navigation Jump to search

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 should 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. But this tutorial does not quite deal with very artificial constructor-computer rules like JvN29.)

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 binary presence(1)/absence(0) to phase difference. In terms of cellular automata, the following patterns can serve as signals:

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, when synchronized, can be 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 (i.e. population count is not fixed for many CAs) nor notion of potential difference in a force field (i.e. translational invariance is held for almost every CA rules).

How to find these building blocks

Constructing signal circuitry involves both human idea and computer power. Here are 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.

The shown 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. Two half-diagonals is a full-diagonal (1fd), and one half of a half-diagonal is a quarter-diagonal (1qd).

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.

The glider gun has a period of 30, making a stream of gliders with apparent gaps. Indeed, gliders can be packed more densely; the minimum separation is 14 ticks, as can be seen in the period-14 glider gun. However, attempts to put a glider somewhere so that it goes across the stream perpendicularly unaffected will fail. Actually, the period needs to be at least 38 for two glider streams in order to be permeable:

x=49, y = 27, rule = B3/S23 2bo$obo$b2o3$46bobo$46b2o$47bo2$11bo$12bo$10b3o3$38bo$36b2o$37b2o3$21b o$19bobo$20b2o3$27bobo$27b2o$28bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 ]]

This fact motivates us to find higher-period glider guns. We can simply arrange two period-30 glider guns and see how the gliders interact.

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 gliders 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 deletion, or
  • are clean unity or over-unity reactions themselves.

Yet, the 90-degree kickback reaction can be sometimes useful. In the following pattern, two gliders bounce back and forth between two period-30 streams of gliders, deleting every other glider and resulting the following glider gun:

x=74, y = 71, rule = B3/S23 67b2o$67b2o6$44bo$42b3o$41bo$41b2o24b3o$66bo3bo$65bo5bo$65bo5bo$68bo$ 66bo3bo$67b3o$68bo3$69b3o$69b3o$68bo3bo$62bobo$62b2o3b2o3b2o$25bo37bo$ 25b2o20bo$24bobo18bobo$46b2o2$3b2o51bo$3b2o49b2o$55b2o$17b2o$18b2o49b 2o$17bo51b2o3$47bobo$47b2o$10bo37bo$2o3b2o3b2o20bo$9bobo18bobo$bo3bo 25b2o$2b3o$2b3o36bo$39b2o$40b2o$5bo$4b3o$3bo3bo$5bo$2bo5bo$2bo5bo23bob o$3bo3bo24b2o$4b3o26bo9$5b2o$5b2o3$17bobo$17b2o$18bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 WIDTH 600 HEIGHT 600 ZOOM 8 AUTOSTART GPS 8 LOOP 120 ]]

(Note: the mechanism has an overall period of 120, but the output glider stream is period-60. We consider this as a pseudo-period 60 glider gun. )

The other 2-glider collisions are not clean, as they leave some debris after interaction. These may also increase the period of a glider stream; as an example, the following true-period p60 glider gun uses a block-making reaction.

x=53, y = 39, rule = B3/S23 23bo$23bobo$26b2o6b2o$12b2o12b2o4bo3bo$12b2o12b2o3bo5bo$23bobo4b2obo3b o8b2o$23bo7bo5bo8b2o$32bo3bo$34b2o$24bo$22b2o$23b2o6$15bobo$15b2o$16bo 4bo$20b2o$20bobo6$28b2o$27b2o$29bo$39b2o$37bo3bo$obo25bo7bo5bo8b2o$2o 26bobo4b2obo3bo8b2o$bo15b2o12b2o3bo5bo$17b2o12b2o4bo3bo$31b2o6b2o$28bo bo$28bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 HEIGHT 400 WIDTH 600 ZOOM 8 AUTOSTART GPS 8 LOOP 60 ]]

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 two:

x=104, y = 43, rule = B3/S23 18bo59bo$18bobo57bobo$21b2o6b2o50b2o6b2o$7b2o12b2o4bo3bo35b2o12b2o4bo 3bo$7b2o12b2o3bo5bo34b2o12b2o3bo5bo$18bobo4b2obo3bo8b2o35bobo4b2obo3bo 8b2o$18bo7bo5bo8b2o35bo7bo5bo8b2o$27bo3bo55bo3bo$29b2o58b2o$19bo59bo$ 17b2o58b2o$18b2o58b2o6$o9bobo48bo8bobo$b2o7b2o50b2o6b2o$2o9bo49b2o8bo 4$12bo59bo$11b2o58b2o$11bobo57bobo6$19b2o58b2o$18b2o58b2o$20bo59bo$30b 2o58b2o$28bo3bo55bo3bo$19bo7bo5bo8b2o35bo7bo5bo8b2o$19bobo4b2obo3bo8b 2o35bobo4b2obo3bo8b2o$8b2o12b2o3bo5bo34b2o12b2o3bo5bo$8b2o12b2o4bo3bo 35b2o12b2o4bo3bo$22b2o6b2o50b2o6b2o$19bobo57bobo$19bo59bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 400 WIDTH 1000 ]]

Why are both included here? Because we start to take color and parity into consideration. As stated above, the relationship between two gliders is described with the concepts of color and parity. As they are independent considerations, there is a total of 2 × 2 = 4 combinations of preserving and changing cases.

However, the color-changing/preserving and parity-changing/preserving considerations are actually insufficient for arbitrary glider timing adjustments. Suppose two 90-degree reflectors are combined into a flexible 180-degree reflector. By moving in or out the composite device by one full diagonal, the path length will be changed both on the outward lane and the inward lane, thereby advancing or delaying the glider by 4 × 2 = 8 ticks. A partial solution is to swap the two 90-degree reflectors when one is color-changing and the other is color-preserving; this changes the timing by 4 ticks. Yet, we still need to develop mechanisms at different mod-8 timings for a complete toolkit.

Another consideraion is called repeat time, or recovery time; it measures the temporal difference between two succesive signals that can be reflected successfully. As demonstrated below, one of the reflectors above has a repeat time of 60 generations.

x=59, y = 43, rule = B3/S23 33bo$33bobo$o35b2o6b2o$b2o19b2o12b2o4bo3bo$2o20b2o12b2o3bo5bo$33bobo4b 2obo3bo8b2o$33bo7bo5bo8b2o$42bo3bo$44b2o$34bo$32b2o$33b2o6$15bo9bobo$ 16b2o7b2o$15b2o9bo4$27bo$26b2o$26bobo6$34b2o$33b2o$35bo$45b2o$43bo3bo$ 34bo7bo5bo8b2o$34bobo4b2obo3bo8b2o$23b2o12b2o3bo5bo$23b2o12b2o4bo3bo$ 37b2o6b2o$34bobo$34bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 400 WIDTH 600 ]]

Signal inverter/NOT gate/AND (NOT) gate

A Boolean logic NOT gate, or signal inverter, takes an input and gives an inverted output. When fed with a glider at certain timing, the device should not emit any glider; if no glider enters, it should emit gliders periodically. Such mechanism processes binary digital data, not analogue ones; it won't work if the glider's timing is incorrect.

It is easy to see that two-glider annihilation reactions is the key to inversion:

x=49, y = 36, rule = B3/S23 42b2o$42b2o6$obo$b2o$bo$42b3o$41bo3bo$40bo5bo$40bo5bo$8bo34bo$9b2o30bo 3bo$8b2o32b3o$43bo3$44b3o$44b3o$43bo3bo$37bobo$37b2o3b2o3b2o$38bo4$23b o$24b2o5bo$23b2o4b2o$30b2o2$44b2o$44b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 400 WIDTH 600 ]]

From this, it seems that a hole (vacancy site) among an intermittent stream of spaceships is similar to a single spaceship traversing the vacuum in terms of the signal carried. NOT is the most basic operation done to such a stream, and it does not destroy nor create information.

A related operation is AND (NOT), that is, a two-input AND gate with one of its inputs inversed first. We don't actually need a AND gate to do this, though; the following will work. There is an output glider if there is the northeast glider and not the northwest glider:

x=71, y = 12, rule = B3/S23 o19bo19bo19bo$2bo5bo12b2o5bo13bo5bo12b2o5bo$2o4bo13b2o4bo13b2o4b2o12b 2o4b2o$7b2o18b2o18b2o18b2o5$7b2o18b2o18b2o18b2o$7bo19bo19bo19bo$8b3o 17b3o17b3o17b3o$10bo19bo19bo19bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 400 WIDTH 600 STOP 40 ]]

An eater absorbes the extra northwest glider in case it doesn't get annihilated.

OR gate

A Boolean logic OR gate takes two inputs and gives an output. When fed with at least a glider at certain timing, the device should emit a glider at the same timing. It is the inverse operation of NOR.

The simple fact that A NOR B = 1 AND ( NOT A ) AND ( NOT B ) allows for the construction:

x=79, y = 46, rule = B3/S23 24bo$22bobo$12b2o6b2o$11bo3bo4b2o12b2o$10bo5bo3b2o12b2o$2o8bo3bob2o4bo bo$2o8bo5bo7bo$11bo3bo$12b2o$23bo$24b2o46b2o$23b2o47b2o4$39b2o$39bo12b obo$30bobo4bobo12b2o$31b2o4b2o14bo$31bo$72b3o$71bo3bo$70bo5bo$30bo39bo 5bo$30b2o6bo34bo$29bobo7b2o30bo3bo$38b2o32b3o$73bo3$74b3o$38b2o34b3o$ 39bo5bobo25bo3bo$36b3o7b2o19bobo$36bo9bo20b2o3b2o3b2o$68bo4$53bo$54b2o 5bo$53b2o4b2o$60b2o2$74b2o$74b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 600 WIDTH 800 STOP 120 ]]

Alternatively, a suitable three-glider annihilation can also work in place of two AND (NOT) gates.

x=79, y = 46, rule = B3/S23 24bo$22bobo$12b2o6b2o$11bo3bo4b2o12b2o$10bo5bo3b2o12b2o$2o8bo3bob2o4bo bo$2o8bo5bo7bo$11bo3bo$12b2o$23bo$24b2o46b2o$23b2o47b2o6$30bobo$31b2o$ 31bo$72b3o$71bo3bo$70bo5bo$46bo23bo5bo$38bo5b2o27bo$39b2o4b2o24bo3bo$ 38b2o32b3o$73bo3$37b2o35b3o$38b2o34b3o$37bo7bobo25bo3bo$46b2o19bobo$ 46bo20b2o3b2o3b2o$68bo4$53bo$54b2o5bo$53b2o4b2o$60b2o2$74b2o$74b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 600 WIDTH 800 STOP 120 ]]

Try disabling the northeast glider or the southwest one to see the effect.

Now that an OR gate (and of course a NOR gate) is ready, we may draw the conclusion that this signal circuitry is universal to the same extent as some other implementations of the well-known universal NOR logic — but wait a moment! There are some other issues.

Signal duplicator/fanout and memory storage

A signal duplicator takes an input and gives two outputs. It is the simplest case of a fanout (or a splitter), i.e. devices that increase the number of signals.

The period-60 glider gun above shows that a block-synthesizing reaction can consume two gliders in a row, performing NOT operation twice. Then apply NOT again and positive signals are emitted well:

x=130, y = 73, rule = B3/S23 30bo$28bobo$18b2o6b2o$17bo3bo4b2o12b2o$16bo5bo3b2o12b2o$6b2o8bo3bob2o 4bobo$6b2o8bo5bo7bo$17bo3bo$18b2o$29bo$30b2o$29b2o3$47bo$45b2o$46b2o$ 36bobo$37b2o$37bo$96b2o$96b2o3$44bo$45b2o76b2o$44b2o77b2o4$95b3o$94bo 3bo$51bobo39bo5bo$52b2o39bo5bo$24bo27bo43bo$22bobo69bo3bo24b3o$12b2o6b 2o73b3o24bo3bo$11bo3bo4b2o12b2o60bo24bo5bo$10bo5bo3b2o12b2o15bo69bo5bo $2o8bo3bob2o4bobo26b2o6bo64bo$2o8bo5bo7bo25bobo7b2o31b3o26bo3bo$11bo3b o43b2o32b3o27b3o$12b2o78bo3bo27bo$23bo76bobo$24b2o65b2o3b2o3b2o$23b2o 76bo23b3o$125b3o$124bo3bo$118bobo$118b2o3b2o3b2o$108bo10bo$30bobo76b2o $31b2o75b2o$31bo4bo$36b2o36bo19b2o$35bobo37b2o17b2o16bo$74b2o34b2o$ 111b2o2$125b2o$125b2o$28b2o$29b2o$28bo$17b2o$16bo3bo$5b2o8bo5bo7bo$5b 2o8bo3bob2o4bobo$15bo5bo3b2o12b2o$16bo3bo4b2o12b2o48bo$17b2o6b2o63b2o 5bo$27bobo59b2o4b2o$29bo66b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 800 WIDTH 1200 STOP 300 ]]

This is essentially a way to retrieve information. One of the outputs can be circulated back to input:

x=136, y = 128, rule = B3/S23 106bo$106bobo$109b2o6b2o$95b2o12b2o4bo3bo$95b2o12b2o3bo5bo$106bobo4b2o bo3bo8b2o$106bo7bo5bo8b2o$115bo3bo$117b2o$107bo$105b2o$106b2o5$99b2o$ 99b2o2$104bo$103b2o$103bobo3$92bo$90b2o$91b2o$111b2o$110b2o$112bo$73b 2o47b2o$74bo45bo3bo$74bobo34bo7bo5bo8b2o$75b2o34bobo4b2obo3bo8b2o$100b 2o12b2o3bo5bo$100b2o12b2o4bo3bo$114b2o6b2o$111bobo$83bo27bo$82b2o$82bo bo6$90b2o$89b2o$91bo5$98bo$97b2o$30bo66bobo$28bobo$18b2o6b2o$17bo3bo4b 2o12b2o$16bo5bo3b2o12b2o$6b2o8bo3bob2o4bobo$6b2o8bo5bo7bo74b2o$17bo3bo 82b2o$18b2o86bo$29bo86b2o$30b2o82bo3bo$29b2o74bo7bo5bo8b2o$105bobo4b2o bo3bo8b2o$94b2o12b2o3bo5bo$47bo46b2o12b2o4bo3bo$45b2o61b2o6b2o$46b2o 57bobo$36bobo66bo$37b2o$37bo$96b2o$96b2o3$44bo$45b2o76b2o$44b2o77b2o4$ 95b3o$94bo3bo$51bobo39bo5bo$52b2o39bo5bo$24bo27bo43bo$22bobo69bo3bo24b 3o$12b2o6b2o73b3o24bo3bo$11bo3bo4b2o12b2o60bo24bo5bo$10bo5bo3b2o12b2o 15bo69bo5bo$2o8bo3bob2o4bobo26b2o6bo64bo$2o8bo5bo7bo25bobo7b2o31b3o26b o3bo$11bo3bo43b2o32b3o27b3o$12b2o78bo3bo27bo$23bo76bobo$24b2o65b2o3b2o 3b2o$23b2o76bo23b3o$125b3o$124bo3bo$118bobo$118b2o3b2o3b2o$108bo10bo$ 30bobo76b2o$31b2o75b2o$31bo4bo$36b2o36bo19b2o$35bobo37b2o17b2o16bo$74b 2o34b2o$111b2o2$125b2o$125b2o$28b2o$29b2o$28bo$17b2o$16bo3bo$5b2o8bo5b o7bo$5b2o8bo3bob2o4bobo$15bo5bo3b2o12b2o$16bo3bo4b2o12b2o48bo$17b2o6b 2o63b2o5bo$27bobo59b2o4b2o$29bo66b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 1200 WIDTH 1200 ]]

What's special about this loop? It stores information and sends them repeatedly. By adjusting its memory we can make a stream of gliders distributed in, say, a ...1101000... sequence:

x=136, y = 128, rule = B3/S23 106bo$106bobo$109b2o6b2o$95b2o12b2o4bo3bo$95b2o12b2o3bo5bo$106bobo4b2o bo3bo8b2o$106bo7bo5bo8b2o$115bo3bo$117b2o$107bo$105b2o$106b2o5$99b2o$ 99b2o2$104bo$103b2o$103bobo3$92bo$90b2o$91b2o$111b2o$110b2o$112bo$73b 2o47b2o$74bo45bo3bo$74bobo34bo7bo5bo8b2o$75b2o34bobo4b2obo3bo8b2o$100b 2o12b2o3bo5bo$100b2o12b2o4bo3bo$114b2o6b2o$111bobo$83bo27bo$82b2o$82bo bo6$90b2o$89b2o$91bo5$98bo$97b2o$30bo66bobo$28bobo$18b2o6b2o$17bo3bo4b 2o12b2o$16bo5bo3b2o12b2o$6b2o8bo3bob2o4bobo$6b2o8bo5bo7bo74b2o$17bo3bo 82b2o$18b2o61bo24bo$29bo51b2o33b2o$30b2o48bobo31bo3bo$29b2o74bo7bo5bo 8b2o$105bobo4b2obo3bo8b2o$94b2o12b2o3bo5bo$47bo46b2o12b2o4bo3bo$45b2o 61b2o6b2o$46b2o57bobo$36bobo66bo$37b2o$37bo$96b2o$96b2o2$66bo$44bo21b 2o$45b2o18bobo55b2o$44b2o77b2o4$95b3o$94bo3bo$51bobo39bo5bo$52b2o39bo 5bo$24bo27bo43bo$22bobo69bo3bo24b3o$12b2o6b2o73b3o24bo3bo$11bo3bo4b2o 12b2o60bo24bo5bo$10bo5bo3b2o12b2o15bo69bo5bo$2o8bo3bob2o4bobo26b2o71bo $2o8bo5bo7bo25bobo40b3o26bo3bo$11bo3bo77b3o27b3o$12b2o78bo3bo27bo$23bo 76bobo$24b2o65b2o3b2o3b2o$23b2o76bo23b3o$125b3o$124bo3bo$118bobo$118b 2o3b2o3b2o$108bo10bo$30bobo76b2o$31b2o75b2o$31bo4bo$36b2o56b2o$35bobo 56b2o16bo$110b2o$111b2o2$125b2o$125b2o$28b2o$29b2o$28bo$17b2o$16bo3bo$ 5b2o8bo5bo7bo$5b2o8bo3bob2o4bobo$15bo5bo3b2o12b2o$16bo3bo4b2o12b2o48bo $17b2o6b2o63b2o5bo$27bobo59b2o4b2o$29bo66b2o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 1200 WIDTH 1200 ]]

Exercise: XOR gate and AND gate

OR, XOR and AND are three symmetric two-input Boolean logic gates whose outputs are not trivially all 0's. When an XOR gate is fed with only one of the two gliders at certain timing, the device should emit a glider at the same timing; otherwise the output has no glider. An AND gate emits a glider iff both glider inputs are fed.

Building these gates is within NOR logic's capability, but can they be simpler? Sure! Now their construction is left to the reader as an exercise.

Hint: there is already an AND (NOT) gate. Another hint: a key XOR reaction is

x=10, y = 13, rule = B3/S23 8bo$7bo$7b3o2$2bo$obo$b2o4$4b2o$4bobo$4bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 4 ZOOM 1 ]]


We have demonstrated the signal circuitry technology with gliders, eaters and period-30 Gosper glider guns. Its diverse possibility with simple components has attracted Life enthusiasts since inception, applications of which goes from a Rule 110 unit cell and deep cell to pulsar pixel raster line display and Remini self-constructing puffer. Further discussion on the forums can be found here and here.

There is lots of room for future advancement.

  • About the signal: we have used gliders only, going at a fixed direction and speed. However, there are also other signal carriers such as the period-4 c/2 orthogonal spaceships LWSS, MWSS and HWSS, the perturbation in a diagonal 2c/3 wire, and even methuselahs Herschel, B-heptomino, etc. In some cases information transmission and interaction may be better with some of them. But developing other signal circuitry needs pretty different methods, as can particularly be seen in the history of Herschel circuitry.
  • About the signal devices:
    • Their bounding box cannot be ignored. Sometimes it may be too bulky, in particular the clearance may be poor in some direction, so that it needs compactifying.
    • Their timing should be treated carefully. When shifting a period-30 device so that input glider path lengthens by, say, N full-diagonals, the phase of the device should be delayed by 4N ticks at the same time, which is inconvenient. Stable circuitry has only one phase, so they do not need to be adjusted. On the other hand, there are many patterns at different periods other than 30 that are equally capable of building signal circuitry with.
    • Their mechanism can be more diverse.
      • The inner workings of a Gosper glider gun has not been discussed above, instead it is used as a whole. As a result we missed things like an inline inverter and the following duplicator.
x=49, y = 27, rule = B3/S23 25bo$25bobo$8b2o18b2o4b2o$6bo3bo17b2o4b2o$2o3bo5bo16b2o$2o2b2obo3bo8bo 4bobo$5bo5bo9bo3bo$6bo3bo5bo2b3o$8b2o5$28bo8bo$26bobo6bobo$27b2o4b2o 12b2o$20bobo10b2o12b2o$18bo3bo10b2o$11b2o5bo8b2o6bobo$11b2o4bo4bo3bo2b o7bo$18bo8b2o$18bo3bo$20bobo2$35b2o$35bobo$35bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 ]]
      • Other patterns with period being a factor of 30 (i.e. p15 pentadecathlon, p3 bumper and p5 bumper) or a multiple of 30 (i.e. p120 Simkin glider gun) exist, and they no doubt can be incorporated in period-30 technology. Even period-1 still lifes can be employed; we missed another small duplicator using a block mentioned in the fanout article.
      • Can transient (unstable, short-lived) patterns play a part? Yes! As a glider can be reflected by dying sparks, as shown below with duoplet and banana spark, there could be a larger class of reflectors (e.g. a buckaroo) that are not based on 2-glider annihilations, hopefully completing the mod-8 timing toolkit requirement above.
x=18, y = 5, rule = B3/S23 2bo10bo$obo8bobo$b2o9b2o$4bo10b2o$3bo13bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 16 ]]
  • The constructions so far, or rather, drawing and copy&pasting, have been done manually. For a self-replicating system (like the aforementioned Remini), everything has to be built and destructed by the pattern itself. This is far beyond the scope of this way too basic tutorial, though; more knowledge about building a seed and using a professional program is required.

In the following sections, we will briefly see how signal circuitry can be developed in other cellular automata without the familiar glider. Prerequisities including signal and its source & sink are in fact easy to satisfy for many alien rules. For those who concentrates on Game of Life, these can be skipped.

Example 2: Banks-I, with the wire

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. It was proposed as a CA modelling a general-purpose computer. In this rule, 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 period-2N "clock", or in essence, signal factories. In addition there is a fanout wire junction and a 90-degree reflector.

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 ]]
x=75, y = 28, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 14b5o30b5o$15b3o32b3o$15b3o32bobo$15b3o32b2o$15b3o32b3o$15b3o32b3o$15b 3o32b3o$15b3o32b3o$15b3o32b3o$15b3o32b3o$o14b3o32b3o$3ob14o15bo16b3o$ 2ob31o16b3o$15o3b16o15b4o$o12b2o3b16o16b3o$13b2o3b3o12bo16b3o$12b4o2b 3o28b4o4bo$18b3o30b7o16bo$18b3o30b24o$18b3o30bo6b17o$18b3o37b17o$18b3o 37bo15bo$18b3o$18b3o$18b3o$18b3o$18b3o$17b5o! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 WIDTH 800 HEIGHT 500 ]]

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 and growing configuration, the domino replicator, that messes up every random pattern:

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

However, the replicator can be tamed by itself. Thus, four such replicators form a stable period-4 oscillator:

x=7, y = 7, rule = B2a/S 2bo$2bo$2o2$5b2o$4bo$4bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 16 ]]

Two copies of this loop bounds another replicator, making a period-64 shuttle:

x=111, y = 7, rule = B2a/S 2bo105bo$2bo105bo$2o107b2o$39bo$5b2o32bo64b2o$4bo101bo$4bo101bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 WIDTH 1000 ]]

A column of these shuttles at adequate spatial and time offsets serves as the railway for another replicator to run in a single direction:

x=111, y = 87, rule = B2a/S 2bo105bo$2bo105bo$2o107b2o$55bo31bo$5b2o48bo31bo16b2o$4bo101bo$4bo101b o10$2bo105bo$2bo105bo$2o107b2o$39bo$5b2o32bo64b2o$4bo101bo$4bo101bo10$ 2bo105bo$2bo105bo$2o107b2o$23bo31bo$5b2o16bo31bo48b2o$4bo101bo$4bo101b o10$2bo105bo$2bo105bo$2o107b2o$71bo$5b2o64bo32b2o$4bo101bo$4bo101bo10$ 2bo105bo$2bo105bo$2o21b2o84b2o$55bo31bo$5b2o48bo31bo16b2o$4bo101bo$4bo 101bo10$2bo105bo$2bo105bo$2o107b2o$39bo$5b2o32bo64b2o$4bo101bo$4bo101bo! #C [[ THEME 6 GRID THUMBNAIL THUMBSIZE 2 ZOOM 8 HEIGHT 1000 WIDTH 1000 ]]

That's it, a signal! Elaboration on the scheme is up to the reader.

Example 4: Live Free or Die, with the puffers and rakes

Live Free or Die (B2/S0) is an explosive rule. There are small spaceships and puffers and rakes; with several reactions such as catch and throw, fly-by deletion and reanimation, a Rule 110 simulator has come to life. In-depth analysis is also up to the reader.


Be innovative! There are lots of wonders on the journey of alien signal circuitry. To summarize the idea:

Before setting off, search for interesting patterns. The components of signal circuitry — still lives, oscillators, spaceships, guns, methuselahs and many thing else — can arise in random soup searching, for example. Advanced patterns like conduits and catalysts require sophisticated search utilities and ideas.

Make sure what will be the signal, and list its properties. Compare with the glider above in case you are not sure what to do. Good signals are small and common/natural ones.

Construct signal source and sink (if these cannot be found, then probably you need to turn to other signals), and then, construct devices based on signal interactions.

Build complex patterns (infinite growth at different rates, unit cell for different CAs, even engineered spaceships if equipped with knowledge on construction, etc), post them to the Other Cellular Automata subforum in the Conwaylife.com forums, have fun and profit (e.g. getting an entry in OCADOTY)!

As for the classical Game of Life, well, good luck with crazy, brand new applications!