The Domino Computer
As part of the Manchester Science Festival 2012, Matt Parker decided to demonstrate how computers worked by building one out of dominoes.
This page will show you how the domino computer was designed — here is the official video from the weekend, but be aware it contains answers to some of the interactive domino puzzles below.
The computer comprised about ten thousand dominoes, and could add up any two three-bit numbers to give a four-bit number (although only once). I was part of the team which built it, and helped design the layout.
The aim is to demonstrate how very simple reactions, simple enough that they occur in real physics, can be combined to perform mathematical calculations — which hopefully helps explain how large numbers of transistors can combine to play Doom.
Matt has also produced these explanatory worksheets aimed at teachers, and this Numberphile video which goes a little deeper into the workings of the domino computer.
The computer is made of “wires”, which are made of normal domino chains. They work much the same way as the connections in a normal, electrical circuit, although there are a few important differences, notably that they can only be used once. Try dragging a domino wire from the blue “trigger” dominoes on the left to the green “display” dominoes on the right.
(If you’re reading this on a mobile device, you might not be able to add dominoes, but you should be able to cheat your way through using the “reveal answer” buttons — or play along when you get back to a computer with a mouse.)
Press “play” or click the blue trigger area to watch the dominoes fall.
You can also split a signal in two. Try hitting both of these output areas:
This is a little pointless since the two arms are exactly the same, so let’s try adding an input. We program our domino computer by adding dominoes in certain places. In this case, we’re going to add two yellow “input” areas partway along the floor. Click one of the input areas to turn it on and off. This time, hit the top output area only if the top input area is on, and similarly for the bottom one:
Let’s try something a little more complex: this time, try to trip the bottom output panel if the input is activated, and the top one if it isn’t. (The output areas will turn red or green when you toggle an input area, so you can see what you’re going for.) There is probably more than one sensible answer to this one, but I’ve included mine in case you get stuck. If you need a hint, think about how to stop the signal to the bottom output.
These sim-dominoes can only fall exactly forward or backward, so bear that in mind when you're stopping a line.
You can always remove a domino by clicking on it, or start again by clicking “clear”.
What we’ve built here is a NOT gate: the top output is active if and only if the input isn’t. Let’s try to build some other gates. The easiest one to make is the OR gate: try to get the output active if either (or both) of the inputs are:
Next, try an AND gate: trigger the output panel only if both inputs are active:
If you’re like me, you just drew a chain of dominoes through both input panels. This is entirely correct, but can’t really be combined with other gates, so isn’t very useful for building a computer. Try doing it without placing any dominoes in the grey area:
(If you need a hint, think about how you built the NOT gate — the solution is surprisingly similar. At least, mine is. There are others.)
The last common logic gate is XOR, or “exclusive or”. In this case, you need to activate the output if exactly one of the inputs is active. If both or neither are, nothing should happen:
(If you need a hint, bear in mind that any piece of domino “wire” can be used exactly once. And this one is hard: it’s probably fine if you click “reveal answer” on this one.)
Four years later, to go with the world’s slowest computer, we built the world’s lowest framerate RGB display.
The trick to building a binary adding machine, or indeed any computer, is combining these simple gates into something more complex. Specifically, the next step in our chain is the Half Adder. This essentially outputs a 2-bit binary number (00, 01, or 10) representing the number of inputs which are active. Try to activate the top output if exactly one input is active, and the bottom if both are. (You may have to scroll or expand this one.)
It’s useful to realise that this is simply an XOR gate and an AND gate on the same board, although you may find you can’t use the same designs as before because there isn’t room or because you can’t easily cross domino wires. A little lateral thinking can produce a solution, though, and you can always reveal my answer if you get stuck.
By now you’re probably starting to get nearby rows of dominoes knocking each other over, and blocking lines arriving after the signal has got through. These are problems we encountered on our second attempt at building a domino adder. We got overambitious and tried to build a four-bit adder in the same space, with the same number of dominoes. But these are problems faced by real electronics: signal can bleed from one line to a nearby one, and electric signals do not travel instantly, so timing can be an issue in very fast chips.
Perhaps predictably, the next step is a Full Adder. This takes three inputs, and again outputs a 2-bit number (now 00, 01, 10 or 11) representing the number of inputs which are active. Where the Half Adder can add two one-bit numbers, the Full Adder is designed to also accept a “carried” one from the previous digit (which we aren’t doing yet). The finished computer will be essentially a series of Full Adders.
There is a clue in the name as to how to get from a Half Adder to a Full Adder, but it’s not a simple task.
The last step is to connect the Full Adders together. To add two three-bit numbers, we used two Full Adders and one Half Adder (because the first digit never has anything carried into it). The XOR outputs from the Adders, and the AND output from the last Full Adder become the four digits of the display, and the AND outputs from the first two adders become the “carried” digit input for the two Full Adders. This leaves two inputs on each Adder. These are where we input our two binary numbers to be added.
Real dominoes are not as well behaved as the pretend ones you are using. They’re all different shapes and you can’t test it before you start. Therefore the entire system was designed to use only one junction design. We tested that one junction design meticulously, and it worked every time.
It’s also impossible to be sure how the timings will play out, so many parts of the circuit were much larger than they probably needed to be, to make sure everything would happen in order.
The last thing to remember is that each Adder can only be toppled when the previous one has completed, otherwise we won’t know if there’s a one to carry. Therefore the “trigger” line for each one is activated either by the carry line from the previous Adder, or from a “clock” line. The job of the clock line is to activate the Adder if nothing is carried. The clock line is therefore very long and bendy to ensure it never triggers an Adder before the carry line can get there.
I’m not going to make you build the entire domino computer with your mouse, but you’ve built every major component of it now. If you scroll back to the top and watch the video (again), perhaps you’ll be able to see all the XOR gates and Full Adders as they fall.