Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Build a computer using dominoes

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15574
46
• 6
You can build AND and XOR circuits using dominoes. And with these, you can build a computer of arbitrary complexity.

fred rosenberger
lowercase baba
Bartender
Posts: 12235
36
holy crap!!! That was amazing!!!

Arun Giridhar
Ranch Hand
Posts: 181
My next weekend Project!

Paul Clapham
Sheriff
Posts: 21443
33
Archimedes wrote:Give me a large enough table and I will build the world's biggest computer!

Bear Bibeault
Author and ninkuma
Marshal
Posts: 65279
95
Mind. Blown.

Piet Souris
Rancher
Posts: 1403
29
Brilliant!

But for me, the most brilliant is: when a heavily loaded truck passes by, you end up with mere ones, no matter what input.

chris webster
Bartender
Posts: 2407
33
Piet Souris wrote:Brilliant!

But for me, the most brilliant is: when a heavily loaded truck passes by, you end up with mere ones, no matter what input.

That'll be the ONO gate...

Chan Ag
Rancher
Posts: 1089
14
Awesome.

Ryan McGuire
Ranch Hand
Posts: 1086
4
• 1
That one configuration of dominoes he uses where one line knocks a couple dominoes from a second line out-of-line so that the second row stops seems to be the lowest level basic gate, which is used to make the slightly higher level AND gate. If we call main line of dominoes "line X" and the line that might knock a couple pieces out of X "line Y", the basic gate implements X AND NOT Y. When a single input was tied to both inputs of that low-level gate, it implemented A AND NOT A, which should always be false. Indeed, the output of that set up was never triggered. Then the second input (B) and low-level gate were added. That second gate implemented A AND NOT B. The output of that was routed to the second gate, which yielded A AND NOT (A AND NOT B). A little elementary boolean algebra will convince us that that does indeed reduce to A AND B.

Given a low-level A AND NOT B gate is it possible to implement all the other possible unary and binary functions? If so, how? If not, why not?

Mike Simmons
Ranch Hand
Posts: 3090
14
• 2
No, it's not possible.

Given two inputs:

A
B

if we add one gate, there are 4 ways to do it, and we have 3 possible results:

A AND NOT B
B AND NOT A
FALSE

(FALSE is obtained by gating either A AND NOT A, or B AND NOT B.)

Now, given these five possible values:

A
B
A AND NOT B
B AND NOT A
FALSE

if we add one more gate connecting any two of these, there are 25 possibilities (21 new) we get one additional possible value:

A AND B

But now, if we consider these six possibilities, and all the ways we might apply one more gate to them (36 possibilities, 11 new):

A
B
A AND NOT B
B AND NOT A
FALSE
A AND B

There are no new combinations possible. Every single gate combining two of those lines results in a value already listed in one of those lines. So there is no point to adding any more gates; every possible circuit is equivalent to one of those already listed. There's no way to do a NOT, or an OR. Or a TRUE, or a NAND, or an XOR. We simply can't construct about half of the possible operations we might need. No way, without access to some other gate type.

Fun question though - thanks!

Stephan van Hulst
Bartender
Posts: 6486
83
• 1
Race conditions must be a sob to debug.

Ryan McGuire
Ranch Hand
Posts: 1086
4
Mike Simmons wrote:...
There are no new combinations possible. Every single gate combining two of those lines results in a value already listed in one of those lines. So there is no point to adding any more gates; every possible circuit is equivalent to one of those already listed. There's no way to do a NOT, or an OR. Or a TRUE, or a NAND, or an XOR. We simply can't construct about half of the possible operations we might need. No way, without access to some other gate type.

Fun question though - thanks!

Of course, there are ways to make other types of gates. e.g. An OR gate might look like this from above:

Without doing an exhaustive search as Mike did, I would venture that we still can't implement all of the possible unary and binary gates given A AND NOT B and A OR B low-level gates. However, I am excited that we can at least do an XOR now.

A XOR B = (A AND NOT B) OR (B AND NOT A)

Jayesh A Lalwani
Rancher
Posts: 2762
32
There is a theory called functional completeness. Basically, if you can mathematically prove that the 3 primary boolean operators AND, OR, and NOT can be implemented using a certain kind of logic gate, the gate is considered an universal gate. It can be used to implement any logic circuit

SOmewhere in the 30s some smart aleck showed that a NAND gate is functionally complete, which is what lead to vacuum tubes being used to implement logic circuits, which lead to invention of logic circuits being controlled by punch cards, which lead to the idea of general purpose logic circuits being controlled by instructions on cards, which is what lead us here.

First of all, few of the properties of boolean algebra

Something ANDed with true is itself
A = AND(A, TRUE)

you can convert an AND operation to a OR operation. Basically
AND(A,B) = NOT(OR(A,B))
OR(A, B) = NOT (AND(A,B))

Also, 2 NOTS cancel each other. So
A = NOT (NOT(A))

So,.. this is how you do an NOT operation with a NAND gate

NOT(A) = NOT(AND(A, TRUE)) = NAND(A, TRUE).. easy peasy

This is how you do an AND operation

AND(A, B) = NOT(NOT(AND(A, B))) = NOT(NAND(A,B)) = NAND(NAND(A,B),TRUE)

This is how you do an OR

OR(A, B) = OR(NOT(NOT(A)), NOT(NOT(A))) = NOT(AND(NOT(A),NOT(B))) = NOT(NOT(NAND(NOT(A),NOT(B)))) = NAND(NAND(A,TRUE),NAND(B,TRUE))

Someone else discovered.. hey vaccum tubes can acts as NAND gate. What the OP has implemented above is a NAND gate, even though he calls it AND. You can just reverse the meaning of the dominoes and it becomes a NAND gate.

Ryan McGuire
Ranch Hand
Posts: 1086
4
Jayesh A Lalwani wrote:
What the OP has implemented above is a NAND gate, even though he calls it AND. You can just reverse the meaning of the dominoes and it becomes a NAND gate.

If you're talking about the bigger gate that he made up of two low-level gates, I disagree. Using the mapping of "falling down" is TRUE, and "standing up" is FALSE. Then he does indeed have an AND gate: Input A falling down and input B falling down leads to the output falling down. Any other combination of inputs leads to the output dominoes not falling down.

If you reverse the meaning so that falling down is FALSE and standing up is TRUE, he has an OR gate. i.e. The only set of inputs that leads to a FALSE (falling down) output is two FALSE (falling down) inputs, and anything else leads to a TRUE (standing up) output.

In fact I would go as far as to say you can't create a NAND, a NOR gate or a NOT gate out of dominoes, regardless of the mapping of truth values you assign to the falling versus standing lines of dominoes. Why? because domino logic gates are "passive" elements. i.e. The best they can do is stop energy (a falling line of dominoes) from passing through under certain conditions. They can't spontaneously start a falling line of dominoes if none of the input lines are falling.

However, I do agree with your analysis that you can create any other type of gate given just NAND gates.

Mike Simmons
Ranch Hand
Posts: 3090
14
Note also that the OP didn't implement this - he pointed us to a video by the guy who did implement it. And I agree with Ryan, an "AND NOT" is not, and cannot be made equivalent to, a NAND. Sure, with NANDs you can implement everything; we know this. But try implementing a simple NOT or OR using only AND NOT. You won't be able to.

Ryan McGuire wrote:In fact I would go as far as to say you can't create a NAND, a NOR gate or a NOT gate out of dominoes, regardless of the mapping of truth values you assign to the falling versus standing lines of dominoes. Why? because domino logic gates are "passive" elements. i.e. The best they can do is stop energy (a falling line of dominoes) from passing through under certain conditions. They can't spontaneously start a falling line of dominoes if none of the input lines are falling.

Ah yes, excellent way of looking at it. I agree. This also suggests an out - if we require a single line of dominos to be tipped, as a "do it" command to execute an operation, then we can achieve anything else we want to. (Well, with sufficient time, care, patience, and dominos.) This would provide us with a known "true" value (notably absent on my previous list) which would also allow NOT (since T AND NOT A == NOT A) and thus enable NAND and all other binary gates we might desire. It's roughly analogous to requiring the user to press "enter" at the end of a command.

Henry Wong
author
Marshal
Posts: 21780
85
Mike Simmons wrote:
Ryan McGuire wrote:In fact I would go as far as to say you can't create a NAND, a NOR gate or a NOT gate out of dominoes, regardless of the mapping of truth values you assign to the falling versus standing lines of dominoes. Why? because domino logic gates are "passive" elements. i.e. The best they can do is stop energy (a falling line of dominoes) from passing through under certain conditions. They can't spontaneously start a falling line of dominoes if none of the input lines are falling.

Ah yes, excellent way of looking at it. I agree. This also suggests an out - if we require a single line of dominos to be tipped, as a "do it" command to execute an operation, then we can achieve anything else we want to. (Well, with sufficient time, care, patience, and dominos.) This would provide us with a known "true" value (notably absent on my previous list) which would also allow NOT (since T AND NOT A == NOT A) and thus enable NAND and all other binary gates we might desire. It's roughly analogous to requiring the user to press "enter" at the end of a command.

This is also how many more complex gates works. There is a trigger that will send the inputs to the outputs. Of course, this is mainly for timing purposes -- meaning give time for the inputs to settle, then send a clock signal, to send the result to the outputs. This same technique can be applied here -- and an XOR gate is basically a NOT gate, where one signal is the input and the other signal is the enable trigger.

Henry

Stephan van Hulst
Bartender
Posts: 6486
83
The "clock pulses" would have to have great intervals to allow parts of the circuit to be rebuilt