Images from “Marble Runs and Turing Machines”

I just returned from this year’s G4G11, where I presented my work on the computability of marble runs (with some success- while I did finish my slides, I went almost 2 and a half minutes over time despite editing and practicing my talk. PROTIP: Don’t go on a two-day vacation 4 days before a conference whose third major theme was sleep deprivation!) I promised I would post the full construction for a marble-run computer here, which not only shows that the double-switch marble run halting problem is PSPACE-Complete, but also should enable simple proofs of universal computability for many other systems. But enough with the jargon; this is going to be more of a slideshow-style post, although I’ll soon post a more in-depth explanation of my talk. (The original slides are also available here, which also includes notes on the script.)

But first, some acknowledgements. The very first image, an example of a marble machine, was taken directly from denha’s fantastic video, “Marble machine chronicle“. While denha’s Youtube channel focuses primarily on marble machines, the electronics videos are certainly interesting as well, so definitely check it out. I used Blender for most of the non-schematic animations, so thanks to the people behind the animation engine and Cycles Render. And finally, the proof would undoubtedly have been much more difficult without the ideas of Demaine, Hearn, and Demaine (choose your own ordering), not to mention the many other people who’ve done work on computational complexity theory and all the things that led up to the field. (I’m sure some would prefer I name-checked everybody involved, but then I’d have to include my kindergarten teacher and the crew behind the Broome Bridge and, well, this would be a lot longer.)

So, without further ado, here are the various images and videos from my talk, presented in substantially more than 6 minutes.

This is, as mentioned above, denha’s “Marble machine chronicle”, for those who have never heard of marble runs under that particular name before.

 

I made (with assistance from Peter Bickford) a short video demonstrating a few recurring elements in marble machines- specifically, the ones I would be analyzing later in the talk. The original marble machine, from the Tech Museum of Innovation,  also contains a few other elements (such as loop-de-loops, chimes, and randomized switches), some of which do nothing to the computational ability of the machine, others which actually do change the problem a bit. Additionally, I consider problems with exactly one marble or pool ball, although Hilarie Orman suggested that it might be possible to simplify the construction using two or more pool balls.

 

This is a decoy that looks like a duck, used for a quick gag and counterexample to the Duck test. This was actually the shortest clip and the longest render for the entire project; the good news was, it rendered at 24 times the speed of a Pixar film. The bad news was that it rendered at only 24 times the speed of a Pixar film.

 

pvpcA short slide made to demonstrate the proof that single-switch marble machines cannot emulate a computer (unless NP=PSPACE, which is really unlikely). Up top, we have the problem we’re trying to solve, while on the lower-left is a randomly generate marble run with edges annotated and on the right is a system of equations representing said marble run. (Click through to see the rest of the images)

 

The next simplest thing is a double switch, which is essentially two single switches ganged together so that they always have the same “value”. This was a bit of a problematic slide because the second half, showing a marble entering the front switch, then the back, actually hadn’t finished rendering by the time I went on stage.

 

UsefulGadgetThese next four videos show how this particular gadget works, and how it emulates a single, amnesiac memory cell… most of the time. All of the schematics were generated using a custom animation and drawing package designed for marble runs within Mathematica.

 

n-switchInterestingly, given two switches ganged together, you can get any positive integer of connected switches! Here’s a larger image of the construction (imagine the switch has been rotated 90 degrees clockwise):ntoggleThis is composed of three modules fed by two main loops, which you can think of as train stops:

Essentially, it works a bit like this: We start by getting on the right train loop, and then ride the train around each station, getting out and drawing two chalk lines- red and blue, say- at every stop. We’re pursuing a hypocritical campaign against red chalk lines, though, so the moment we see a red chalk line we get out and erase it, and since we drew that line, we’re at the same station we originally started at. (You’ve probably figured this out by now, but each station is a module, the presence of a red chalk line is the state of the top double switch, and the presence of a blue chalk line is the state of the middle, long double switch). We immediately take out our orange chalk and draw a “campaign against red chalk” logo, and then board a train with specially tinted windows so that we can’t see anything blue, while still getting out at every station and erasing the red chalk marks. (We only draw the logo when exiting the first train.)

But once we don’t see a red chalk mark, we draw a red chalk mark and are about to board the first train when we see the red chalk mark (that we just drew) and remove it. Since we just exited the first train, we attempt to draw our logo, but see it’s already there and (apparently ashamed) erase it. (We’re now in the lower-left corner of the video.) We see the blue mark, and erase it while drawing a purple mark and a white mark. But whenever we draw something with the white chalk, we remember we have to clean or draw something with the blue chalk, at which point we see the purple mark (while erasing it) and finally erase the white mark. Every time we erase a white mark, we check to see if we’re holding a piece of blue chalk, which we are. In total, we’ve toggled the presence of a blue mark at every station and wound up at the same station we started at, holding a piece of blue chalk if and only if every station now has a blue chalk mark, with at most two rules per piece of chalk (depending on whether we came from the left or the right train).

Another way of looking at it is that the top double switch records the answer to the question “have I been here before?”, while the long middle double switch records the answer to the question “what is the state of the emulated n-switch?” We start out by toggling both types of switches until we’ve been somewhere before, at which point we start toggling only the first type of switches until we’ve never been somewhere before. We use an extra switch to remember whether we’re writing or erasing, located in the upper-left, and finally the gizmo in the lower-left simply reads the value of a switch without toggling it.

functioncallslide This is a “function call” gadget, which takes x as an input, and returns the marble along the track corresponding to the ordered set {x, f(x)}. It does this by using some really long switches and a linear array search: It stores the input, computes f(x) and stores that in a (2m+1)-switch, reads the input, and moves right across the (2m+1)-switch array until it sees a 1 (Right), at which point it exits. (Here, m is the number of inputs, and n is the number of ouputs.). In schematic form, the marble will exit at output n*x+f(x).

 

tapecellslideThis is the first part of a tape cell gadget, which allows you to store any integer within a range and read the stored value.

tapecellslide2You can use that inside a function call gadget to exit through a particular output once set to create a gadget which is much easier to work with. By this point, we’re not actually even working with the original double and single switches any more, which is not necessarily bad, but seems to imply that a few things could be simplified and/or micro-optimized. In fact, this particular gadget could use a pair of n-switches in place of the function call.

 

This is a quick and not fully defined block diagram of a Turing machine- “move left or right” should read “move left or right on the tape”. (Additionally, the version of this in the working slides had “set new state” written twice.)

 

turingblocksThis is a more formalized version of a Turing machine, which is essentially equivalent to the previous diagram, but which explicitly arranges the paths and set/read sections of the block diagram.

 

marbleturingFinally, if you replace each block in the above diagram with the necessary construction, you get the above, which looks complicated but is still essentially equivalent to the above. This finishes the construction of the polynomial-space Turing machine and proves that double-switch marble runs are PSPACE-Complete. (The above picture is actually of a maximal 3-state Busy Beaver, which sets every single tape cell on the right. The entirety of the “programming” of the computer is contained within the connections above each of the three tape cells in the bottom-middle.)

By the way, all of the schematics above were constructed in Mathematica as functions, which means that you can actually tweak the number of inputs and outputs and have the schematic automatically change- except for the final Turing machine construction, which was stymied only by the deadline.

Interestingly enough, this proof is actually simpler if you try to construct a simulation of Conway’s Game of Life in the double-switch marble run system instead of a polynomial-space Turing machine; Since the Game of Life can emulate a register machine, which is Turing-Complete, a simulation of the Game of Life on a bounded grid should be PSPACE-Complete. Furthermore, a computer which simulates the Game of Life can be easily constructed using only the n-switch construction (along with double switches and ramps and the other base elements), although this hasn’t been tested yet (the idea came too late for the conference).

 

g64

This is by no means practical for a modern-day computer. The above 3-state Busy Beaver alone has 259 single switches, 852 double switches, and 3,756 paths (determined by a Python program), and if you wanted to simulate a laptop processor along with 4GB of memory, you would need a marble run about 1/5 the diameter of the Sun. (At this point, it starts generating its own gravity, and then the marble might get stuck, and all sorts of bad things start happening.) But the important thing is that marble runs can compute anything!

In particular, if a particular system can move an object from any place to any other place (as much as necessary) and emulate a double switch, then this shows that it can automatically emulate a Turing machine, and so that the problem of determining that system’s output is PSPACE-Hard. (The slides said -Complete, which is in PSPACE-Hard, but very likely not the same)

Finally, here are two extra questions which at the moment remain unsolved:

Is the construction simpler if there are two marbles? For instance, can you use the timing of marble lifts as memory? (From Hilarie Orman)

Can you construct a crossover gate in 2D?

If you have answers to either (or both) of these questions, I’d appreciate it if you could contact me at (rot13) grpuvr314@tznvy.pbz .

Oh, and one other thing: I plan to get Random (Blog) back up and running in the next few months, so stay tuned.

 

 

  1. Very cool, Neil! It was great to see you in Atlanta. You may have made me lose all my marbles trying to understand any of this!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 38 other followers

%d bloggers like this: