Domino Computation

I try to explain this so that someone with no technical background can understand it, but I go pretty quick in an effort not to bore those who already know this stuff. I hope I found the right balance for you, if not, jump to the pictures and videos. This describes how I worked out how to make a computer (well, calculator) with dominos. If such a thing doesn’t interest you, you better not read any further.

Introduction

I’ve been interested in primitive and alternative computation since I learnt that computers were made of pretty much nothing but switches. 10 years ago, I was thinking of pneumatic computers, when I first met roo we had a discussion about computers made of wood and elastic bands or cockroaches, and chatting to woodly got me thinking about computers made of dominos.

Theory

To really make a complete computer, I’d need a NOT gate, which sadly is pretty complicated with dominos - I figure you’d need a clock and a mechanism to stand dominoes back up again - I’m imagining a piece of string tied to the pendulum of a grandfather clock, something like that anyway…

Luckily though, you can make some useful computation circuits without the NOT gate. To make things as simple as possible, we restrict ourselves to binary numbers (poor old Babbage, doing everything in base 10). Binary numbers are just another way of writing numbers, any whole number can be easily represented as a binary number - it works just like decimal, except that the individual places never go above 1, and each position doubles the value of the digit instead of increasing by 10 times. 101 in decimal is a hundred and one (1×100 + 0×10 + 1×1), whereas 101 in binary is five (1×4 + 0×2 + 1×1). Adding two numbers together is the same as in base 10 as well, except instead of carying 10, we have to carry 2.

Here’s the longhand calculation for the decimal sum 574 + 927 = 1501

4 + 7               = 1 (carry 1)
7 + 2 + 1 (carried) = 0 (carry 1)
5 + 9 + 1 (carried) = 5 (carry 1)
0 + 0 + 1 (carried) = 1

And now the longhand for the binary sum 101 + 11 = 1000 (in decimal, that would be 5 + 3 = 8)

1 + 1               = 0 (carry 1)
0 + 1 + 1 (carried) = 0 (carry 1)
1 + 0 + 1 (carried) = 0 (carry 1)
0 + 0 + 1 (carried) = 1

You can see that in binary you’d need loads more digits to represent the same number, but that it simplifies things because you only ever have to deal with 0 and 1 (if only the Nintendo Brain Training game only gave me sums with 0 and 1 in them). Looking at the steps we took, you can see that in order to add two numbers together of any size (in decimal or binary), you need to do many steps of adding together 3 numbers of only one digit. We take a digit from one, a digit from the other, and the carry from the previous calculation, and produce a digit for the answer, and the carry for the next step.

When working with binary there are relatively few possibilities so it can be nice to see these things in a table. On the left are all the possible inputs, and on the right are the outputs we want. This is called a truth table, and this is the truth table for what’s known as a Full Adder.

a b c
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
sum carry
0 0
1 0
1 0
0 1
1 0
0 1
0 1
1 1

In dominos, it makes sense to represent a 1 as the dominos being knocked down, so, this table tells us that if we could create a series of dominos that had 3 input lines of dominos that resulted in two output lines, where the first was knocked down if one or all three of the input lines were knocked down, and the second was knocked down if two or more of the input lines are knocked down, then we can build a sequence of dominos to add any number together.

Actually coming up with a domino chain to do that is pretty complicated, so I simplified the problem again. Rather than adding three numbers, you can create something simpler that only adds two numbers, and chain two of them together so that it ends up adding 3 numbers. This simpler component is called a half adder, and the truth table looks like this.

a b
0 0
0 1
1 0
1 1
Sum Carry
0 0
1 0
1 0
0 1

If you can make a half adder, then you can stick two of them together to make a full adder. If we can make a half adder in dominos, this means that we could stick a bunch of them together and if we had enough of them, add any two numbers together, simply by flipping some dominos and reading out the result.


Practice


So can I make a half adder in dominos? Here’s the planning for the sum part.

Planning for the sum part of the half adder.

My sum design used two “Inhibit pass through” gates and an Or gate. The inhibit pass through gate is a domino gate I invented that only lets one of the two input lines continue. The truth table looks like this

a b
0 0
0 1
1 0
1 1
output1 output2
0 0
1 0
0 1
0 1

In domino terms, we have two lines of dominos going in, and two coming out. There’s a middle domino that twists depending on which hits it first, and so only allows one of the lines to continue. An OR gate is really easy in dominos, just have two lines merge, and the resulting line will fall when either of it’s input lines falls. With that I was able to create the sum part.

The complete SUM domino circuit.

The final part of the half adder is the carry. This only falls if both of the inputs fall, it’s also called an AND gate. I stuck a few dominos together to make a large domino that would fall if hit, but only if a blocking domino placed side on to it also fell. Here’s a close up of it being blocked by the side-on domino.

Close up of the AND gate.

Result

So, with everything together, does it work?

Domino Half Adder, Input 00, result 00
Domino Half Adder, complete

Domino Half Adder, Input 10, result 10

Domino Half Adder, Input 01, result 10

Domino Half Adder, Input 11 result 01

Yes. Given enough time and dominos I could build a domino chain to add numbers of arbitrary size.

Thanks to Sarah who helped with the filming, and Woodly who discussed the idea with me, and encouraged me to build it.

Update: Bonerici has constructed a domino computer using his own domino logic gate, an XOR constructed in quite a cunning way. I haven’t tried building one yet, but it looks good, and enables a domino computer more palatable to the purists (who were never happy with me sticking dominoes to each other).

Update: A lego half adder.

29 thoughts on “Domino Computation

  1. Pingback: Roo Reynolds - What’s Next? » Blog Archive » Normal service is resumed?

  2. This is very, very cool. A friend pointed me at your site because he knows of my interest in alternative computing. Now I’m trying to think how we could incorporate your stuff into our on-going “Heath Robinson Rube Goldberg (HRRG) Mixed Technology Computer” project.

    If you have a moment, check out the following page that summarizes this project http://www.diycalculator.com/sp-hrrgcomp.shtml (at the top of this paper there’s a link to a series of articles on an IBM site that are documenting our progress in building “The Beast”

    Cheers — Max Maxfield (www.DIYCalculator.com)

  3. So, this article got slashdotted, and I’ve been unable to get to my server for a day or so. Thanks to everyone for their interest, sorry it “fell over” so quickly (yes, almost all of the comments on slashdot were jokes about domino servers).

    Someone pointed out this site which designs a similar thing, although there’s no cool videos. He also took a more traditional approach and built a NAND gate, but as I moaned, a NOT gate has issues in dominos. He overcame it with a sync line, a nice solution, but it is a little bit tedious to have to fire a bunch of non input lines to do your calculation.

    Some people complained that I was cheating with the sticking together of dominos for my AND gate. I suppose that for the domino computing purist (and I’m sure there are many of them), I probably was cheating. If anyone wants to suggest a better AND gate, I’m all INBOXes.

    Some commentators spotted that I pinged one of the domino lines a bit harder than the other in the videos and hypothesized that it was all a fix and it’d taken me many takes to get it right. Actually, the system was more robust than I expected, but even with some sneaky sellotape hinges to stop them sliding around too much, it was still very tedious to reset them, so in fact all of those were done in one take each. There wasn’t any reason I pinged it harder, but when I watched back and realised, I couldn’t be bothered to do another take.

    Some people didn’t see how it is a computer. I can understand that, and until I can build a full one (for which I’ll need a lot of dominos and manpower), you’ll have to take it on trust that “real” computers, even when they’re playing Doom, are really not doing anything significantly more advanced at the minature scale. Maxs site, the DIY Calculator may help with that.

    Max, that HRRG computer is fantastic, I want one! It’d be cool to have a section that does some part of a calculation in dominos. You should definitely have a section using insects and light bulbs as well….

    And finally, I’d like to thank my friends, family. etc. without whom none of this would have been possible…

  4. Fascinating work!!!

    I’m amazed that even after slashdotting, nobody has pointed out that your truth table for the full adder is incorrect. You omitted this case:

    abc == 110

    Of course, that wouldn’t affect your video play – and the play’s the thing (with apologies to the Bard).

  5. Great Idea !
    To have many full adders work together, I think the problem will be in “how would you design the delay?” I mean, if the input to the 2nd phase is a=1, b=1, c=1, would it be possible to guarantee they will knock their corresponding domino pieces at the same time? or we may get a=1, c=1, work before b=1 [steady] is reached? :-)

  6. Ahmed, I think this may be a little problem, but it would be possible to fix, just by lengthening the appropriate lines that were going too quickly. At every level, we want the inputs occuring more or less together, and we should be able to build a half adder component where the outputs do happen more or less together by lengthening the output that happens too soon in each of the half adders. It is a slight ugliness though, it’s true.

  7. Pingback: Die Schatenseite: Weblog » Rechnerstrukturen: Der Halbaddierer

  8. Okay, I can’t believe you haven’t thought of this, but my friend and I were trying to replicate this. I saw the article on slashdot, but the site was down, so I didn’t know exactly how to set it up. However, we had the idea of making a half-adder using an XOR, and implementing NAND. a XOR b = (!a NAND b) NAND (a NAND !b), according to what I derived.

    Anyway, we couldn’t implement NOT, but we did implement AND, and it worked pretty well. Here’s how you do it.

    1) Set up two dominoes at a right angle. They should be nearly touching.
    2) Put a domino on front so that if one of these dominoes falls like it should, it won’t collide with this.
    3) Put leading dominoes to the two right-angled inputs. Make sure they are symmetrical, so the timing is right.

    This works because when one domino falls, it simply falls off to the side, avoiding the domino in front (the output). When they both fall, however, they push against each other, providing equal, opposite force, but gravity still pulls them forward, crashing into the output domino. This should be a suitable AND.

    Cheers!
    Nick

  9. Hey Nick, How about a picture? Or you could post videos of it working as responses on YouTube. It’s an ingenious solution, but it sounds like it’s pretty dependant on timing. My gates are a little dependent on timing, but they have a lot of leeway.

    Maybe now that you’ve got to the site, you could create a better design? I’d love to see it.

  10. You should be able to make any gate, including inverters, by using a dual-rail encoding, and you wouldn’t need any tricks like making large dominos: Instead of representing a 1 by having a line fall and a 0 with no fall, you have 2 lines, one for each value. I think your inhibit pass-through gate would work as the inverter.

  11. I know this wouldn’t meet with the purists taste, but why don’t you mount the dominoes to rails? Could be something simple like the plastic “hot wheels” race track and a finishing nail into the side to act as a hinge. That would make reseting easier.

    On top of that, connect string to the top of the dominoes so you could actually have a reset string.

    Using the hinge and a reset string, it would now be pretty easy to have a “not” domino holding up a weight to pull on a section of reset string.

    Very interesting idea. I would have never thought to build a computer out of dominoes. I have thought of pneumatics and water works, but this is very fun to watch.

    Reg

  12. Pingback: domino domination « There goes rhymin Simon

  13. I’ve been intrigued by using dominoes and other chain-reaction devices to build a computer. I’ve even came up with practical AND, OR, and a NOT gate using the ‘herringbone’ technique. While I have the basic logic gates and a memory of some sort, even doing a simple calculation could easily take up a room full of falling popsicle sticks.

    If anybody out there is serious about trying to build a computer out of dominoes or sticks, please go to my Kinetic Art page and drop me an e-mail if you’re interested in a possible project…

  14. Hey! I was interested in building a half adder purely out of dominos, so I too set out to try it. The machine I constucted wasn’t at all like this one, but it worked. However, it had two problems. Number one, it needed a “clock pulse” signal after the numbers were inputed, which worked but would be hard to implement if two or more half adders were stuck together. The second problem was that it involve “intersections”, to lines of dominos crossing, and sometimes one line would set off the other line and this would mess things up. The design on this site is much better. Thanks!

  15. One suggestion for improvement. You AND gate looks like it’s kind of iffy in that it might not always work properly, plus it requires you to stick dominos together. A better way to make the AND gate is like this.

    Lay one domino down flat. Then, stick two dominos packed together on the very end of the one that’s laying down flat. Next, take three dominoes packed together and put them next to the end of the flat one that has the two on it, but put the three perpenducular to the two. When the two dominos packed together are hit, they won’t be able to push through the three. But, if the three were first knock out of the way from the side, then when the two are hit they can topple over and hit the ouput chain.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>