wood burning stoves*
The moose likes Meaningless Drivel and the fly likes Build a computer using dominoes Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "Build a computer using dominoes" Watch "Build a computer using dominoes" New topic
Author

Build a computer using dominoes

Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14345
    
  22

You can build AND and XOR circuits using dominoes. And with these, you can build a computer of arbitrary complexity.



Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11477
    
  16

holy crap!!! That was amazing!!!


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Arun Giridhar
Ranch Hand

Joined: Mar 10, 2012
Posts: 148

My next weekend Project!


hate Professionalism . Join the http://2014.hack.lu/index.php/Main_Page
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18902
    
    8

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

Joined: Jan 10, 2002
Posts: 61648
    
  67

Mind. Blown.


[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
Piet Souris
Ranch Hand

Joined: Mar 08, 2009
Posts: 687
    
  11
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

Joined: Mar 01, 2009
Posts: 1848
    
  16

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...


No more Blub for me, thank you, Vicar.
Chan Ag
Bartender

Joined: Sep 06, 2012
Posts: 1049
    
  15
Awesome.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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

Joined: Mar 05, 2008
Posts: 3018
    
  10
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

Joined: Sep 20, 2010
Posts: 3649
    
  17

Race conditions must be a sob to debug.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1012
    
    3
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
Bartender

Joined: Jan 17, 2008
Posts: 2433
    
  28

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

Joined: Feb 18, 2005
Posts: 1012
    
    3
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

Joined: Mar 05, 2008
Posts: 3018
    
  10
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
Sheriff

Joined: Sep 28, 2004
Posts: 18988
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3649
    
  17

The "clock pulses" would have to have great intervals to allow parts of the circuit to be rebuilt
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Build a computer using dominoes