Dominoe Computer

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 1s, but can’t produce any if there are none to start with. Fortunately we can produce an infinite sequence of 1s 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 1s; 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.