Simple Computation Using Dominos

An anonymous reader writes "When silicon fails to beat Moores law, maybe dominos can help. This guy has created a half adder in dominos as a proof of concept for domino computation. If he intends to make a full domino computer he's going to need an awful lot of dominos."

Yes but...

[MrNaz]

I was going to say "Yea but does it run Linux?", but I thought I could avoid the resulting -1 Redundant mod down to hell by saying "Yea, but are there Vista drivers for it?" instead.

Re:

[MrShaggy]

in soviet Russia, adders halfvyou!

Solves for x in 30 minutes or less

[Teresita]

I'm afraid this will open up a half-adder gap with the Deep South. In Alabama, it's illegal to play dominoes on Sunday. (www.dumblaws.com)

Re:Yes but...

[Anonymous Coward]

Gee, let me try:

I was going to say "I wonder if their web server is running on dominos... which fell over already"

"Another crippling bombshell: Netcraft confirms it, domino computers are falling over"

"Imagine a cluster of dominos standing on end, ready to fall over"

"I don't see what you like about OS X. My falling dominos copied a large file in seconds, while my OS X machine has been grinding away for the past 30 years"

"In Soviet Russia, *you* fall over"

"dominos: naked and covered in grits" (if you don't get this one, you must be new here... you insensitive clod)

<meta>Let me be just get it out of the way: here are all the tired Slashdot cliche jokes done in one post</meta> (itself a tired joke! and pointing it out is tired too! come to think of it, I'm tired.)

No No No was:Re:Yes but...

[Anubis350]

"In Soviet Russia, *you* fall over" In Soviet Russia, *you* are the domino, and you pushed over by the state in giant cold war social computer! Domino, the new Cog :-P

You forgot one

[TubeSteak]

Let me be just get it out of the way: here are all the tired Slashdot cliche jokes done in one post (itself a tired joke! and pointing it out is tired too! come to think of it, I'm tired.)

Rest
Cancel or Allow?

You forgot one too

[CrazyJim1]

Don't forget Poland.

I for one....

[LordFocus]

welcome our new Domino overlords.

Re:

[SEWilco]

... delivering half-adders in 30 minutes.

Re:

[drcagn]

Is there a version of Doom ported to this architecture?

Re:Yes but...

[Anonymous Coward]

But of course. It's called Doominos. In fact, in Doominos 3 id left an easter egg in it. It reveals the answer to life, the Universe, and everything.

On the very last level of the game, as you descend the candlelit cavern toward the final boss, take a left at the fork in the path. Find the id Software logo in the back corner. Approach and click your mouse button on the id logo. You'll hear a distinctive "beep" sound. A nearby wall opens to reveal a hidden chamber. The PDA on the altar simply reads "42".

Re:

[Sillygates]

It's probably too slow....with the CPI up in the trillions :(

Re:

[LarsG]

Yes, but idspispopd doesn't work.

Re:

[Equuleus42]

It's meme-rific! All this nostalgia reminded me of the old "Gnulix" flamebait of yore...

Re:Yes but...

[aldo.gs]

1. Try to cite every tired joke.
2. Miss this one.
3. ????
4. Profit!

Re:

[RESPAWN]

"dominos: naked and covered in grits" (if you don't get this one, you must be new here... you insensitive clod)

Wow. I haven't seen the Natalie Portman and Grits joke in a loooooong time.

I think the only "joke" you missed was linking to a redirect page to a Goatse bomb. Can't say I miss those days, though.

(Posting without +1 Karma becuase I know that this is straying waaaaay OT)

Re:

[MarkKB]

Actually, I think it's "In Soviet Russia, dominos knock over YOU!"

Re:

[bhima]

In Korea, only old people use Dominos.

Man, I can't believe I just said that... I'm going for a shower.

Re:Yes but...

[AndroidCat]

Just wait until they get it all setup for a run, go to lunch, and come back to find that Schrodinger's Cat might have been in the room!

Re:

[Belial6]

I don't know, I just wanted to run my Lotus Domino server on it.

Re:

[Punch-Drunk Slob]

Alternate: Yes, but can it do a Black Adder? har har.

Re:

[mwvdlee]

Wierd... I had this exact same idea (building digital logic using dominos) after reading an article of somebody doing digital logic with water, right here on Slashdot.

I never got further than some constructs which would require a customized domino, though.

Too bad TFA is already slashdotted; would have loved to see how he handled dominos staying up because others fell; the NAND.

Re:

[n1hilist]

I was going to suggest a Beowulf cluster but I'd rather not get the -1 redundant post too. So I'm going to make the quirky and even more redundant post about not installing Windows on it at all, because when Windows falls over, it really is going to fall over.

Conceptually, it reminds me of

[TheCouchPotatoFamine]

A turing version [rendell-attic.org] of conway's game of life. But on reflection, if the "dominos" were something like charged nanotubes, then the creation of computing structures could be "grown" in a much different way then current cpu's, kind of think that's neat.

Re:Conceptually, it reminds me of

[QuantumG]

Would you happen to know what the biggest grid of conway ever simulated is? and for how long? I was trying to find stats on this a month or so ago..

Re:Conceptually, it reminds me of

[d34thm0nk3y]

According to here: [pentadecathlon.com]

Andrzej Okrasinski has found a new methuselah record holder, a 15 bit intial pattern with a final population of 1623 after 29053 generations. David Bell quickly found a 13 cell predecessor, bringing the record to 29055.

Re:

[QuantumG]

Yep, pretty interesting, not what I was thinking about though. The population of random soups in Life are also
expected to grow without bound if they are large enough, but only with a vastly large starting size.. analysing soups of extremely large size seems more interesting than studying soups of small size, so I was wondering what the biggest grid size anyone has simulated was. You'd figure we'd be able to do interesting soup sizes by now.

Re:

[spun]

I've done random soups of around five million starting live cells, 10,000 cells on a side at 5% density. That's nowhere near big enough to find any naturally occurring patterns that grow without bounds, though.

Well, i know what would be fun to play with

[TheCouchPotatoFamine]

unfortunatly, i have a mac mini aka 4 shaders.. but this screensaver [mikeash.com] lets you use the video card to do it, so i imagine it's fun to look at.

I just did a search, i didn't find anything about the largest. FWIW i'd LOVE to see the turing version in this screensaver :grin:

Re:

[Fweeky]

Using Golly [sourceforge.net] and a perfectly reasonable desktop computer, I just loaded a ~128k-sq grid with a starting population of roughly 100 million and ran it for 700 million iterations inside about half a minute, so I'm going to bet: pretty big.

Re:

[QuantumG]

damn, you must have a fast machine.. my 2.61GHz AMD Athlon 64 X2 Dual with 4 gig of ram claims it is going to take over an hour and a half just to fill 128k-sq with random.. I can only imagine how long it is going to take to simulate.

Re:

[zobier]

prolly 358^2 not 128000^2

Re:

[Fweeky]

Heh, not really; Opteron 185, 2GB. The pattern was a set of highly repetitive smaller CA's (not unlike this [sourceforge.net]); hash based algorithms are *really* good at accelerating "big" CA's like this.

Re:

[hobdes]

Hmm, I haven't kept up with the research but about 12 years ago I ran a simulation out to 200000x200000. I used a linked list data structure rather than an array to store the data since the typical density of live sites in GL is pretty low (~3%). If you're interested check out Fig 3.27 (page 69) of my MSc thesis [zoology.ubc.ca].</blatant self-promotion> As I recall it took around 3 months to run on one of the latest Sparcstations at the time.

Re:

[hasdikarlsam]

Using golly, I've run the Metacatacryst pattern to 10^11 generations in a matter of minutes, at which point it contained ~10^14 active cells and covered an area of (~10^11)^2 cells. On a common laptop computer - algorithms have improved. :)

This probably is not a great feat these days, but it is quite beautiful to look at. There also exist (rather large) patterns that simulate life /in/ life.

Could make a brainfuck processor!

[EmbeddedJanitor]

A while ago I started with the physical implementation of a brainfuck machine http://en.wikipedia.org/wiki/Brainfuck [wikipedia.org]. A mechanical brainfucker is actually not too hard to do if you compile the BF into the right patterns first.

Re:

[caseih]

On my FC6 box, I did yum install lucidlife, and found, to my surprise, that the turing machine pattern is in it, under "Math and CS." Now if only I could figure out what it is supposed to do! :)

Slight problem..

[QuantumG]

they're one use only gates... you'd need a hell of a big layout just to execute an add of a few bits.

Re:Slight problem..

[AKAImBatman]

they're one use only gates

Nonesense, they're perfectly reusable! You only need to watch out for a metastability period* of 10 minutes between clocks.

* To reset the dominos, of course.

Re:

[QuantumG]

I wonder if there's a way to do self standing dominos.

Re:

[Walt Dismal]

... Domino Viagra ...

Re:

[SQLGuru]

You could do something similar to the Guess Who game to make it easier to reset. Go from 10 minutes down to seconds.....but save that for version 2....no sense trying to jump Moore's law.

http://www.amazon.com/gp/product/images/B00000IWDR /ref=dp_images_1/104-9632234-2647149?ie=UTF8&s=toy s-and-games&img=1&childASIN=B00000IWDR [amazon.com]

Layne

Re:

[tepples]

I wonder if there's a way to do self standing dominos.

Would it have anything to do with Weebles [wikipedia.org], which wobble but don't fall down?

Re:

[Anonymous Coward]

Perhaps some kind of an electromagnetic surface could be used, with one end of each domino having some iron embedded... After the dominoes have toppled, hit a switch that turns on a magnet that pulls them into little slots which turns them upright.

(captcha: delirium ...)

Re:

[iamstretchypanda]

Attention fellow slashdotters!

You know you can't get laid when you:

1. Make a 'computer' out of dominoes
2. Start making jokes about it
3. Realize you spend your day on a website where other people find those same jokes funny
4. Decide a group of dominoes could use an electromagnetic surface and embedded iron to maybe run linux

I also think it's funny when Joe /.er talks about his girlfriend Sally, we all try to pretend he isn't just talking about his right hand he named. :p

Feel free to mod me down, but this ap

Apparently...

[jazzman251]

Apparently the server uses dominoes...

So...

[freeze128]

So, you're saying it's a Domino [ibm.com] server?

Domino Logic

[TheSexican]

This really isn't such an interesting story at all. There is, in fact, a type of CMOS logic called Domino Logic [mit.edu]. So nothing really suprising then.

Re:Domino Logic

[kevinmc]

Here's another site with an explanation of domino logic using real dominos: http://www.pinkandaint.com/oldhome/comp/dominoes/i ndex.html [pinkandaint.com]

Yeah but they use...

[Traf-O-Data-Hater]

...good old-fashioned silicon, not a briefcase substrate like this guy does. And like silicon, you can dope a briefcase too!

Rebooting...

[Anubis350]

No matter how fast he could ever make, rebooting is gonna be one PITA!

Re:

[d34thm0nk3y]

No Anubis. Very few programs are run live, it's a terrible strain on the domino stackers wrists.

From the looks of things...

[Arceliar]

If servers were dominoes, slashdot must be that big and slightly smelly kid who kicks down all your hard work just as you're about to show it off.

Videos on YouTube

[ikegami]

The site might be down, but the videos are on YouTubte

inputs = 0 & 1 [youtube.com]
inputs = 1 & 0 [youtube.com]
inputs = 1 & 1 [youtube.com]

Re:Videos on YouTube

[bidule]

WTF! You slashdotted YouTube!

Re:Videos on YouTube

[UbuntuDupe]

And now, I'm going to say something really stupid, and I don't quite understand why what I'm about to say is stupid. Here goes:

"He didn't build a domino computer, he just has a domino setup whose results under one interpretation coincide with what a half-adder gives you. It's trivial to build any kind of mechanism that can do this."

Now, rhetorically bitch-slap me.

Re:

[CalSolt]

I fail to see a difference. If it acts like a computer- that is, it computes- then it IS a computer. Or does a computer HAVE to have electrons running through it?

Re:

[Stauf]

Not really stupid, but consider - a half-adder is trivial; and an electronic half-adder is just a few wires that when electricity is applied produces the result you would expect from a half-adder.

Re:

[honkycat]

I wouldn't say it's stupid, I would say it's actually a fairly deep sort of question about the nature of computation.

I suspect the reason that you, at least hypothetically, don't see this domino arrangement as a "computer" is that it's both a very trivial computer and it's not suited for scaling into a non-trivial computer by adding more copies. Otherwise, this is not THAT different from a standard electronic circuit. Both are physical systems whose outputs coincide with logical operations. By arranging

Re:

[BarryNorton]

Yes it is a deep question, but the answer was found many decades ago. The answer is that this is computation, but it's not a device capable of universal computation.

Re:

[honkycat]

True enough, but it at least means it wasn't a dumb question, especially for someone not familiar with computer science.

Re:

[honkycat]

Oh, and one other thought... remember that the idea of universal computing is founded on the Church-Turing thesis which is an unprovable hypothesis. Basically, it defines computability as the quality of being something that a Turing machine-equivalent can compute. It's quite possible that there are problems outside this class that can be "computed" but not by a Turing machine equivalent. This is the sort of thing that might be discovered by cleverly forgetting a few of the fundamental things we know abou

Re:

[SuperIan22]

Well, no, of course it's not an actual computer, and it really wouldn't be useful to build a computer out of dominoes. Of course it's kind of pointless, tons of neat things are fairly pointless. But there is something very useful about little demonstrations like this. If you've already got a good grasp of basic computing concepts, it's kind of a big yawn, but for kids who are just learning about a computer's innards, it's simple examples like this that can generate "AHA!" moments. Most people out there hav

Re:

[AlgorithMan]

inputs = 0 & 1
inputs = 1 & 0
inputs = 1 & 1

so, what about inputs 0 & 0?
I won't believe that this thing works until he also shows that result! ;-)

Re:

[had3z]

that's cool and all, but what about 0 & 0?

Re:

[orkysoft]

Well, if you've watched the videos, you'd have seen that your points (1) and (2) have no merit, except for very small values of "shitload".

It explains Notes

[Ritchie70]

I didn't realize that Notes servers use real Dominoes, it explains their awful performance and quirkiness.

Re:

[WS Tu]

In my Slackware+Firefox, it took me 5 minutes or so on "Loading Page" and then gave me a "The connection was reset".

Althrough not quick at all, it is really quirk at all.

Quantum Dot Cellular Automata

[googlebear]

This kinda reminds me of Quantum Dot Cellular Automata. multivalence compounds are arranged like dominos and one of the "electrons" at one of the ends is shifted to represent the zero or one state and then the electron repulsion forces in the molecules propegate down the chain like dominos acting like adders whathave you. http://www.nd.edu/~qcahome/ [nd.edu] -ian

He Cheated!

[haakondahl]

Watch the 1+1 video, and you'll see that the stacked dominoes are actually glued together! No fair!

Details: His right hand pushes over a domino chain which knocks out a link needed to complete the left-hand output. But in order to reach the chain for the left-hand output, he crosses the chain for the right-hand output, which then has a gap. This gap is bridged by GLUING a yellow domino on top of a red one, on top of a blue one.

Re:

[noz]

And you've got too much spare time on your hands.

Re:

[Mal-2]

Even if it's cheating to alter dominoes, it's not cheating to use the same tactic in nanomachines. It will increase complexity to have one piece completely different from all the others, but it's not cheating to use all the options you are given.

Mal-2

Re:

[jmp]

Cheated? What are the rules? Which ones did he break?

Re:

[kyb]

True, but those guys needed loads of extra sync lines. Not very friendly.

Cute

[overshoot]

Of course, we've been using domino logic [princeton.edu] for a long time.

Re:

[TheSexican]

See, I made a similar comment earlier and got modded down by some haters. But maybe your link is better than mine.

Dominoes?

[I don't want to spen]

I thought most computers (or the people who run them anyway) ran on Dominoes, Pizza Hut ... (insert your country's major delivery pizza chain here)

Re:

[Nasarius]

What geek likes bland, undersized, overpriced pizza?

.5+.5=1?

[somethinghollow]

If he intends to make a full domino computer he's going to need an awful lot of dominos.

Like twice as many more? Or does 1/2 adder + 1/2 adder != 1 full adder?

At least he didn't make a death adder.

Re:

[Anonymous Coward]

It's called a "half adder" because it doesn't have a carry bit input, only a carry bit output. With a half adder you can only add 1-bit numbers; with a full adder you can add arbitrary precision binary numbers (in serial).

Re:

[interiot]

http://en.wikipedia.org/wiki/Adder_(electronics)#H alf_adder [wikipedia.org]

Re:

[kperson]

At least he didn't make a death adder.

Or Blackadder.

Re:

[onemorechip]

Two half-adders (plus an OR gate to combine carries) make a full adder, but a "full adder" and a "full computer" are two completely different things. You can put together a bunch of full adders to make a multi-bit adder. Add more logic to perform subtractions, shifts, plus logical and, or, and not operations, and you've got a nice little ALU. Now add some registers, a control store, instruction decoding logic, and a sequencer (complete with conditional branching logic), and you've got a CPU. And to build a

VERY old news

[AlgorithMan]

In computer science study (3rd semester) We have learned that the 2-dimensional infinite domino problem is indecidable

this is because for any turing machine you can design dominos such that you can legally cover the infinite 2-dimensional plane if and only if the turing machine terminates...

so this is nothing new - I guess... I didn't RTFA, but what I read sounds exactly like that...

alright, forget it

[AlgorithMan]

okay, after I saw it as a (not slashdotted *g*) video on youtube, i have to say: this has absolutely nothing to do with what I was talking about...

You can also build a nondeterministic computer

[Bob Hearn]

out of dominoes. That is, if I give you a sliding-block puzzle, where the blocks are all dominoes laid flat in a box, and to goal is to slide one a certain way, that puzzle is a kind of nondeterministic computer.

Details: http://www.dartmouth.edu/~rah/ncl-tcs.pdf [dartmouth.edu]

Domino Time!

[PopeZaphod]

But is he using any Vaz?

IBM's domino computer

[simdan]

IBM actually did some research into using what amounted to molecular dominos for computing. It worked pretty fast, but they literally had to set it up on molecule at a time, and you thought dominos were a pain. They too predict that it might replace transistors. Read more about it here [newsfactor.com].

Re:

[ebers]

I saw Don Eigler present this work. Dominoes were also his analogy. As I remember it was pretty slow, with gates taking many microseconds. Most frustrating was the fact that it was one-shot, with many tedious hours following each computation to rebuild. However, it was amazingly small and very fun to watch.

What is the big deal..

[toygar.ozturk]

What is the big deal, it is only a half-adder. Not even a full one.

Re:

[WS Tu]

I can not read the article. But if they built a half-adder, they can just cascade 2 half adder and got a full-adder.

In fact, at first I guessed I would see the domino logic in VLSI design http://www.princeton.edu/~wolf/modern-vlsi/Overhea ds/CHAP3-4/sld013.htm [princeton.edu]

Next thing you know...

[discHead]

...someone will be using Tinkertoys. [rutgers.edu] :-)

Moo

[Chacham]

Dominoes, a new technology?

Next thing you know, IBM will have a Domino Server.

Turing complete?

[mgiuca]

I assume that Dominos aren't (and will never be) turing complete...?

I mean, each domino can fall over only once. So while you can do an adder, I'm not sure you could really get a for loop going.

Re:

[rbarreira]

You can get them up again, but of course you need energy for that. You also need energy for running an electronic computer.

Re:

[mgiuca]

But then it isn't really using dominos for the turing completeness, is it?

Re:

[rbarreira]

Maybe you're right, but in that case, you also think that just starting the dominos (which clearly is done by an external force) is enough to make it non-turing complete?

Where are the mirrors

[segafreak]

I Know this isn't directly on topic, but for the gazillionth time I get to an article a few hours after it makes Slashdot, and surprise surprise the link is dead because of the Slashdot Effect. I really feel its time slashdot stopped mindlessly killing people's webservers with sheer wight of traffic - if its clearly a small website, why not mirror it?

High speed processing

[Compunexus]

Great! But is only does one FLOP!

My server...

[guruevi]

My server already runs Domino [wikipedia.org], why is he re-implementing this?