Building computers out of sliding block puzzles [pdf] | Hacker News Reader

Building computers out of sliding block puzzles [pdf]

groups.csail.mit.edu

32 pointsColinWright8 comments

Not-so-humble-brag: I am the first author in the first paper referenced in the linked PDF. I came up with the original PSPACE-completeness proof as well as the model of computation from which this is all based. So, yeah, it's kind of awesome to read this 22 years later while browsing HN.

Thank you! Only, I didn't get much past the first page tonight; I built the "dad's puzzle" out of legos and solved it instead...

Well, I accomplished the goal, but far from minimally so.

> Can they be built using only dominoes? The answer is yes, but then they are much more complicated.

The construction may be found in my paper "Limits of Rush Hour Logic Complexity" [1] that also considers oriented sliding pieces of just 1x1, that turn a sliding piece puzzle into a weird kind of maze.

[1] https://tromp.github.io/orimaze.html

Also, as a fun addition, Matt Parker (and others) built [1] a 4 bit binary adder out of about 10,000 dominoes

[1] https://www.youtube.com/watch?v=OpLU__bhu2w

this could perhaps actually be useful at the molecular level as a mechanical computing system. I wonder what possible advantages might be found for micro-mems computation?

They've always seemed terrible to me for speed and thermodynamics reasons (it's so much easier and faster to move an electron than a bunch of neutrons). I suppose from a computational perspective you could do a simple, or set of simple computations in a machine more resistant to, or at least more resilient against, EMP (as the thing that is easy to move in a B field, that electron I mentioned above) is easier to move in undesired wave when subject to a large external B field. I doubt it though.

However you do raise the possibility of longer-lasting computers in other harsh environments, specifically space. The Voyager probes work in part because the feature size of the components is huge (discrete transistors that are inspectable through a microscope and in some cases the naked eye). Such components are hard to come by these days. Micro mechanical devices might even be a superior approach. And for most space applications speed is not critical.

I don't think that you'd ever want to literally have sliding mechanics. However, the dual rail logic used is a type of reversible computation. Thus, thermodynamically it is theoretically much more efficient than standard (irreversible) computation because bits are never erased (which accounts for most of the energy loss).

I was thinking of microscopic mechanical machines; I agree truly sliding would not be optimal.

Reply on news.ycombinator.com