Implementing Logic Gates in the Game of Life

Let's continue writing a binary adder in the Game of Life. In the previous post, we implemented the Game of Life basics and created a module for rendering the population on the screen.

In this post, we're going to learn common patterns in the Game of Life and create ”signals“. At the end of this post, we will create 4 logic gates: NOT, AND, OR, and XOR.

Patterns in the Game of Life

The idea of implementing a computer in the Game of Life isn't new. There are papers and YouTube videos about it. It is because the rules of the game make it turing-complete. It means that we can implement any computable function using only those rules.

As with real computers, our logic gates will depend on signals. In the Game of Life, we can use special patterns called spaceships as signals.

A spaceship is a pattern that can travel across the world. We can use this property to create ”signals flows“.

Glider

The smallest spaceship is a glider. It travels diagonally 1 cell right and down per 4 evolution steps.

We can use a glider stream as a signal. But first, let's implement a single glider:

// main.js

// .O.
// ..O
// OOO

const population = {
  "0:1": createAgent(0, 1),
  "1:2": createAgent(1, 2),
  "2:0": createAgent(2, 0),
  "2:1": createAgent(2, 1),
  "2:2": createAgent(2, 2),
};

const drawer = new Drawer(10);
const world = new World(30, 40, population);

...And then check if this is going to work:

Yay! It's working! However, it is not very convenient to create an initial population using the object. It would be easier if we could use the ASCII pseudo-graphics from the comment above as an argument.

Patterns from Pseudo-Graphics

The ASCII art in the comment above is a part of notation from the Lexicon patterns library.

In this notation, alive cells are described with “O” and dead ones with a dot “.”. Glider in this notation would look like this:

OOO
O..
.O.

There's also RLE format, but it isn't as explicit as just plain text.

Now, let's create a fromPseudoGraphics function which will take an ASCII art argument and return a population:

// composition/from-pseudo-graphics.js

export const LINE_BREAK = "\n";
export const LIVE_AGENT = "O";
export const EMPTY_STRING = "";

export function fromPseudoGraphics(source) {
  const population = {};

  // Split source into lines:
  const rows = source.split(LINE_BREAK).filter(exists);

  rows.forEach((row, j) => {
    // Each line split into characters:
    const characters = row.split(EMPTY_STRING);

    characters.forEach((character, i) => {
      if (character !== LIVE_AGENT) return;

      // If character refers to an alive cell
      // create it and put in the position:
      population[`${i}:${j}`] = createAgent(i, j);
    });
  });

  return population;
}

Now we can save the glider pseudo-graphics in a constant and pass it as an argument to the function:

// main.js

const glider = `
.O.
..O
OOO`;

const population = fromPseudoGraphics(glider);
const drawer = new Drawer(10);
const world = new World(30, 40, population);

It still works but the code is more readable now!

Gosper Glider Gun

We managed to create gliders but it's not enough to create sustainable glider streams. We need some kind of a signal generator.

There are patterns that generate streams of gliders—glider guns.

The simplest gun is Gosper Glider Gun. It shoots gliders with a period of 30 steps. So each 30th step a glider comes out from this pattern.

We can look its ASCII source in the pattern library and take copy it:

// main.js

export const gliderGun = `
........................O...........
......................O.O...........
............OO......OO............OO
...........O...O....OO............OO
OO........O.....O...OO..............
OO........O...O.OO....O.O...........
..........O.....O.......O...........
...........O...O....................
............OO......................`;

const population = fromPseudoGraphics(gliderGun);
const drawer = new Drawer(10);
const world = new World(30, 40, population);

Now, let's check if this is working:

Glider Gun with Period of 60

Gosper Glider Gun shoots with a period of 30. We can use it but it would be better if we made glider streams more sparse.

The denser the stream the more gliders there are to recalculate and rerender. This can negatively affect the app performance, especially on bigger circuits.

We can solve this using a Period 60 Gun. It shoots every 60th step so the stream should be twice as sparse.

// main.js

export const gliderGunP60 = `
............................O..........
............................O.O........
...........OO..................OO......
.........O...O.................OO....OO
...OO...O.....O................OO....OO
...OO..OO.O...O.............O.O........
........O.....O.............O..........
.........O...O.........................
...........OO..........................
.......................................
.......................................
.......................................
.......................................
.......................................
.......................................
.......................................
..........O.O..........................
.........O..O...OO.....................
OO......OO.....OOO.OO..OO..............
OO....OO...O...O...O...O.O.............
........OO.....O.O........O............
.........O..O..OO......O..O............
..........O.O.............O............
.......................O.O.......OO....
.......................OO........O.O...
...................................O...
...................................OO..`;

const population = fromPseudoGraphics(gliderGunP60);
const drawer = new Drawer(10);
const world = new World(60, 80, population);

...And here's the result:

Reflector and Patterns Composition

Sometimes we're going to need to redirect glider streams to make it easier to compose circuits. For this, we can use a reflector.

A reflector is an oscillator that redirects a glider when is hit by it. Let's add a reflector on the field:

// main.js

export const reflector = `
........O
......OOO
.....O...
.....OO..
.........
.........
.........
.........
.........
.........
.........
OO.O.OO..
.........
O.....O..
.........
.OO.OO...
...O.....
.........
.........
.........
.........
...OO....
...OO....
`;

So now we also want to add a glider gun to check if the stream really gets reflected. However, the fromPseudoGraphics function now takes only 1 pattern argument.

To solve this I wrote another module. I won't put the whole source code here but you can always find it on GitHub.

This module's purpose is to apply affine transformations to the pattern using the withSettings functions and then compose different patterns in a single population using the composePatterns function.

// main.js

// Import gun and reflector:
import { gliderGunP60 } from "./life/population/patterns/glider-gun-p60.js";
import { reflector } from "./life/population/patterns/reflector.js";

// Import transformer and composer:
import { composePatterns } from "./composition/composer.js";
import { withSettings } from "./composition/with-settings.js";

// Rotate the gun by 270 degrees,
// reflect the reflector and start it from 13th step:
const gun = withSettings(gliderGunP60, { rotate: 270 });
const reflect = withSettings(reflector, {
  reflect: true,
  phase: 13,
});

// Compose patterns with offsets
// from the top left corner:
const population = composePatterns([
  { pattern: gun, offset: { x: 38, y: 1 } },
  { pattern: reflect, offset: { x: 9, y: 62 } },
]);

// Change the scale a bit:
const drawer = new Drawer(2);
const world = new World(200, 600, population);

The phase argument in withSettings tells how many steps a pattern should “skip” before start. Sometimes we're going to need to change phases of patterns to make sure that gliders hit other patterns at the right time:

If we're mistaken by a single step:

// main.js

const reflect = withSettings(reflector, {
  reflect: true,
  // phase: 13,
});

...Everything's going to blow up ¯_(ツ)_/¯

The synchronization by phase and position was the most time-consuming thing in the whole circuit 😃

In the source code, I added some explanations on how to place patterns to make them “compatible” but still I'm not sure if they are correct 😅

And now — to the gates!

Logic Gates

Logic gate is a device that implements a logic function. These functions take 1 or more arguments and produce either 0 (false) or 1 (true) as a result.

We will use logic gates as basic building blocks for bigger circuits like a half adder and full adder.

NOT Gate

It is easier to start with the NOT gate. The NOT gate is an inverter that flips an input signal from 0 to 1 and from 1 to 0.

Every logic function has a truth table associated with it. These tables enumerate every possible input and corresponding outputs. For the NOT gate, its truth table will look like this:

We'll use truth tables to check if our logic gates work properly.

So, the NOT gate is an inverter. That means that our circuit should “kill” an input signal if there is one and “generate” output if there isn't.

Since we use glider streams as signals we need something to stop the stream. For this, we can use another glider stream directed against the first one.

Glider collisions can result in various outcomes but we're interested in those that “kill” both gliders. Let's direct the clock-gun in such a way that its stream would stop the input signal:

// gates/not.js

const clockGun = withSettings(gliderGunP60, {
  rotate: 270,
});

const signalGun = withSettings(gliderGunP60, {
  rotate: 270,
  reflect: true,
});

const signal = { pattern: signalGun };
const clock = { pattern: clockGun, offset: { x: 38, y: 1 } };
export const not = composePatterns([clock, signal]);

...And check if it's going to work:

Okay, now, let's generate the output if there is no input signal. We will use a reflector to redirect the output:

// gates/not.js

const clockGun = withSettings(gliderGunP60, {
  rotate: 270,
});

const redirection = withSettings(reflector, {
  reflect: true,
  phase: 13,
});

const clock = { pattern: clockGun, offset: { x: 38, y: 1 } };
const router = { pattern: redirection, offset: { x: 9, y: 62 } };
export const not = composePatterns([clock, signal, router]);

Let's check if the output is being redirected:

Now, if the input signal is 0 clock gun shoots gliders into the reflector and this stream becomes the output. If the input signal is 1 it crosses the path of the clock stream, they stop each other and the output becomes 0.

The only thing to do now is to make this gate a function so that it could take input signal as an argument:

// gates/not.js

export function not(input = 0) {
  // If the input is 1 there appears a gun on the left:
  const signal = input ? { pattern: signalGun } : null;

  // Clock gun:
  const clock = { pattern: clockGun, offset: { x: 38, y: 1 } };

  // Reflector will redirect clock stream into the output:
  const router = { pattern: redirection, offset: { x: 9, y: 62 } };

  // Compose patterns together into a population:
  return composePatterns([clock, signal, router]);
}

The whole source code of the gate you can find on GitHub.

AND Gate

The AND gate is a gate that implements logical conjunction. It takes two inputs and returns 1 only if both those signals are true. In other cases, it returns 0.

The truth table for the AND gate looks like this:

For this gate to work, we need to create a configuration of elements so that the output stream would appear only if both input signals are true.

I thought of this:

Signal A is the leftmost, signal B is in the middle, and the clock gun is the rightmost. Their streams are set to “kill” each other if crossed.

So if there is signal B it kills the clock stream and signal A becomes the output. If there is only 1 input signal the clock stream terminates another and the output stays 0.

Let's write the code for this gate:

// gates/and.js

const gunA = withSettings(gliderGunP60, {
  rotate: 270,
  reflect: true,
});

const gunB = withSettings(gliderGunP60, {
  rotate: 270,
  reflect: true,
});

const clockGun = withSettings(gliderGunP60, { rotate: 270 });
const collectorEater = withSettings(eater, { rotate: 270 });

export function and(a = 0, b = 0) {
  const signalA = a ? { pattern: gunA } : null;
  const signalB = b ? { pattern: gunB, offset: { x: 128 } } : null;

  const clock = { pattern: clockGun, offset: { x: 208, y: 1 } };
  const collector = { pattern: collectorEater, offset: { x: 76, y: 173 } };
  return composePatterns([clock, collector, signalA, signalB]);
}

The whole source code for this gate you can find on GitHub.

Graphically this gate is represented with this symbol:

We will use it when building bigger circuits later.

OR Gate

The OR gate is a logic gate that implements logical disjunction. It takes two inputs and returns 1 if at least one of them is true.

The truth table for this gate looks like this:

The element configuration will be similar to the AND gate but with some extra elements. The output this time will be created by another generator. This makes it possible to produce output if there is at least one input signal:

And the source code:

// gates/or.js

export function or(a = 0, b = 0) {
  const signalA = a ? { pattern: gunA } : null;
  const signalB = b ? { pattern: gunB, offset: { x: 128 } } : null;

  const clock = { pattern: clockGun, offset: { x: 208, y: 1 } };
  const output = { pattern: outputGun, offset: { x: 1, y: 45 } };

  const signalCollector = { pattern: collectorEater, offset: { x: 145, y: 161 } };
  const outputCollector = { pattern: collectorEater, offset: { x: 146, y: 206 } };
  return composePatterns([clock, output, signalA, signalB, signalCollector, outputCollector]);
}

There is also a graphical representation for this gate that we will use later:

XOR Gate

The last gate we're going to build today is the XOR gate. It implements the exclusive OR logic function.

It takes two arguments and returns 1 only if either of the inputs is true. If both inputs are true it returns 0.

The truth table for this gate looks like this:

The elements configuration will be a bit more complex. Let's examine it step by step.

First of all, we need to cancel out input signals if they are both true. Let's direct them in opposite directions:

If there is only signal A it terminates the clock stream and the output signal comes out from the output generator:

If there is only signal B it reflects from the reflector, terminates the clock stream and the output signal comes out:

Finally, if there are no input signals the clock stream terminates the output generator.

Let's build the gate in the source code:

// gates/xor.js

export function xor(a = 0, b = 0) {
  const signalA = a ? { pattern: gunA, offset: { x: 48, y: 2 } } : null;
  const signalB = b ? { pattern: gunB, offset: { x: 128, y: 1 } } : null;

  const clock = { pattern: clockGun, offset: { x: 168, y: 44 } };
  const router = { pattern: redirection, offset: { x: 56, y: 105 } };
  const output = { pattern: outputGun, offset: { x: 1, y: 87 } };
  return composePatterns([clock, router, signalA, signalB, output]);
}

Graphical representation for this gate is similar to OR but with some additional details:

...And it's done! I've created demo pages with each gate. There, you can enter input signals and see how the gate produces the output:

• NOT
• AND
• OR
• XOR

What's Next

This time, we created building blocks for bigger gates. Next time, we will use them to create a half adder, full adder, and the 2-bit calculator.

Sources

• Source Code
• 2-Bit Calculator
• Building Circuit Step by Step

Binary Logic

• Let’s BUILD a COMPUTER in CONWAY's GAME of LIFE
• The 10,000 Domino Computer
• Affine Transformation

Binary Logic in the Game of Life

• Conway's Game of Life, PDF
• Turing machine in the Game of Life
• Digital Logic Gates on Conway's Game of Life

Pattern Libraries

• RLE, Run Length Encoded
• Life Lexicon

Gliders, Collisions

• Glider
• Glider on Life Lexicon
• Glider on Conwaylife.com
• Glider in the RLE Format
• Gliders Collision

Other Patterns

• Spaceships
• Guns
• Gosper Glider Gun
• Gosper Gun on Conwaylife.com
• Period 60 Glider Gun on Life Lexicon
• Reflector on Life Lexicon

Logic Gates on Wiki

• Truth Table
• NOT
• AND
• OR
• XOR