• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Build a computer using dominoes

 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Likes 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can build AND and XOR circuits using dominoes. And with these, you can build a computer of arbitrary complexity.

 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
holy crap!!! That was amazing!!!
 
Ranch Hand
Posts: 188
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My next weekend Project!
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Archimedes wrote:Give me a large enough table and I will build the world's biggest computer!

 
Sheriff
Posts: 67746
173
Mac Mac OS X IntelliJ IDE jQuery TypeScript Java iOS
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Mind. Blown.
 
Bartender
Posts: 5465
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 2407
36
Scala Python Oracle Postgres Database Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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...
 
Rancher
Posts: 1090
14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Awesome.
 
Bartender
Posts: 1205
22
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?


 
Master Rancher
Posts: 4806
72
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Saloon Keeper
Posts: 15510
363
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Race conditions must be a sob to debug.
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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)

 
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The "clock pulses" would have to have great intervals to allow parts of the circuit to be rebuilt
 
Thank you my well lotioned goddess! Here, have my favorite tiny ad!
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic