- OEIS
- Archive
- Bettering English
- Concurrency
- Dominoe Computer
- Faster Than Light
- Invariants
- Penrose Maze
- Rust Quickref
- Syntactic Sugar
- Terminal Colors

Suppose you have a whole bunch of dominoes that spring back up precisely three seconds after they’ve fallen down. Can you build a computer out of them?

It turns out that you can. But let’s start out by reasoning about the
basics. To keep things simple, assume we have a big flat 2d floor on which
to stand the dominoes. When playing with dominoes, the typical thing you
do is put them in a line on the floor, and knock one over. Let’s call the
line of dominoes a *stream*, and say that as they fall, a *wave* of
falling dominoes travels down the stream. We’re supposed to be modeling a
computer, so let’s say that a wave represents a `1`

and the lack of a wave
represents `0`

. Of course we can connect several streams together, so call
a bunch of connected streams with some waves a *circuit*.

What sorts of circuits can we build? Let’s start simple. The most basic thing we can do with a stream is put a fork in it. Here’s a diagram:

On the left is a picture of what the tops of the dominoes would look like,
and on the right is a more abstract representation. I’m lazy about
drawing, so we’ll use only abstract drawings from now on. I’ve labelled
this circuit `COPY GATE`

because if a wave comes down from ‘in’, it will
be duplicated to each ‘out’. Hence we can take a bit sequence – that is,
a sequence of waves and lack of waves – and duplicate it.

Ok, so that’s what a fork does. Well, at least that’s what it does if the
wave is coming towards the fork. If we instead put that circuit upside
down, we get an `OR GATE`

instead:

There’s a weakness to our circuits so far: they can duplicate `1`

s, but
can’t produce any if there are none to start with. Fortunately we can
produce an infinite sequence of `1`

s with a simple loop. Since the
dominoes stand back up, a wave in a loop (of sufficient circumference)
will circle it forever, and a `COPY`

gate will emit a `1`

each time it
goes around. Adjusting the circumference of the loop controls the timing
of the sequence.

This can easily be extended to implement *memory*. In the circuit below,
the left input is used to “set” the memory, after which the output is a
sequence of `1`

s; and the right input is used to “unset” it, returning the
output to `0`

.

It’s also possible to build a *diode*; a circuit that allows “current”
(i.e. waves) in one direction but not the other. Here a wave from the left
will run into itself and “cancel out”, while an input from the top will
continue on to the left unimpeded.

We can use a diode and a `1`

input to construct a not gate. To do so, you
have to be very careful about the delays that streams introduce, just like
in a real computer. I’ve labelled parts of this circuit with numbers
indicating how many seconds a wave should take to traverse them. There’s
also two little boxes; these don’t correspond to anything physical, they
just mark interesting locations where waves in opposite directions will
cancel out.

Now we have both OR and NOT gates. It’s well known that these gates
together are *universal*, meaning that they can be combined to construct
any logic gate. For instance, you can construct AND because `x AND y`

is
the same as `NOT ((NOT x) OR (NOT y))`

. (It’s important that we have a ONE
and COPY gate too, though those are usually taken for granted.) Thus we
can build arbitrary logic gates.

Actually, I just lied. Do you see the hidden assumption?

Take a few minutes and think about it: why aren’t the gates I’ve described so far really universal?

When combining various circuits, it’s generally assumed that you can attach any circuit’s output to any other circuit’s input. But can we do that? The floor we’re placing dominoes on is 2-dimensional, and we can’t just have two streams cross because they’d crash into one another.

Fortunately there’s a workaround. There’s a circuit made up of `OR`

and
`NOT`

gates whose outputs are its inputs, but swapped. Below is a
picture. The inputs are labelled `x`

and `y`

, and intermediate values are
labelled. Juxtaposition means `AND`

, `+`

means `OR`

, and a bar on top of
a letter means `NOT`

. Streams splitting and joining together mean `COPY`

and `OR`

gates, as you would expect, and each veritcal bar is a `NOT`

gate. By using this circuit we can swap streams, so with enough of them we
can arrange streams however we need to, and so these circuits really are
universal.

Therefore you can make memory and arbitrary logic gates out of stand-up-again dominoes, and, with enough patience, a general-purpose computer.