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 ”signal flows“.

Glider

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

Glider moving across the field
Glider moving across the field

We can use a glider stream as a signal. (If there’s a flw of gliders—there’s 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:

The created glider moves across the field

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.

# In the RLE format, glider is represented like this:
x = 3, y = 3, rule = B3/S23
bob$2bo$3o!

# Not so obvious, we'll stick to pseudo-graphics.

In order to get a population of cells from a pseudo-graphics, we will write the function fromPseudoGraphics.

As an argument we will pass it a string of pseudo-graphics, which we will divide into lines, and each line into characters. In place of each character O we will create a live cell and fill the population object, which we will then return from the function as a result:

// 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.

Gosper Glider Gun with period of 30
Gosper Glider Gun with period of 30

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:

Every 30 iterations there's a new glider

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:

Every 60 iterations there's a new glider

Reflector and Pattern 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:

When the mutual positioning and phases are fine-tuned, the deflector changes the direction of the gliders

If we’re mistaken by a single step:

// main.js

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

…Everything’s going to blow up ¯\_(ツ)_/¯

Error in phase or position leads to explosions

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:

A NOT A
0 1
1 0

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:

Clock terminates the signal

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:

Reflected signal comes out as the output

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.

How the NOT gate is working
How the NOT gate is working

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:

A B A AND B
0 0 0
0 1 0
1 0 0
1 1 1

Two inputs mean to arguments:

// gates/and.js

export function and(a = 0, b = 0) {
	const signalA = null;
	const signalB = null;
}

that the output stream would appear only if both input signals are true.

I thought of this:

AND gate scheme
AND gate scheme

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:

AND gate
AND gate

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:

A B A OR B
0 0 0
0 1 1
1 0 1
1 1 1

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:

OR gate
OR gate

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:

OR gate
OR gate

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:

A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

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:

1 XOR 1 equals 0
1 XOR 1 equals 0

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

1 XOR 0 equals 1
1 XOR 0 equals 1

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

0 XOR 1 equals 1
0 XOR 1 equals 1

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:

life-xor
life-xor

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

To Be Continued

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

Другие посты из серии

Binary Logic

Binary Logic in the Game of Life

Pattern Libraries

Gliders, Collisions

Other Patterns

Logic Gates on Wiki