Plans for a mechanical Turing machine

This is a project I've been planning for many years. It's a design for a fully mechanical universal Turing machine. My self-imposed constraints are to use no electronic or even electrical components, to be driven by a single rotating input shaft, and to be constructable with simple hand tools, without relying on high precision parts.

Trying to design something like this is an interesting challenge, and something I've found I can work on entirely in my head when I'm stuck somewhere with some spare time and not even as much as a sheet of paper to draw ideas on. Some of you might like to stop reading here and try and figure out a design yourselves before this plan taints you.

I had most of the conceptual design finished at the start of this year, and it's taken until now to get a fully specified model made up in OpenSCAD. I think this is now ready to manufacture.

One of the most difficult initial problems is how to store a reasonable amount of data, such as the tape for a Turing machine without having to manufacture a large number of custom parts. My design uses ball bearings on a sheet of pattern perforated metal as the tape. The position of balls on the grid is the data, and the machine moves back and forward on the grid. To be strictly universal, the perforated metal sheet needs to be infinitely long. I haven't carefully examined the sheet RS have sent me but will assume it to be infinite for the time being.

I'll now try to describe how the rest of the machine works, which is pretty difficult and I don't think this will be immediately clear. I hope to have a working prototype soon which should make its operation clearer.

This schematic diagram shows the main components of the machine.

The next component after the grid and set of ball bearings is a lifting arm or raiser (red) which picks up the 'input symbol' under the read head and lifts it to the top of a block of channels not unlike a marble alley. The run needs to contain some state which will direct the ball down different channels, and needs levers which will update the state for the next ball, and set the direction the machine will move. It also needs to direct the ball back to a new position on the perforated sheet to 'write' the new symbol.

First in the run is the 'state box' (cyan) which diverts the ball down down one of two paths depending on the position of the gate. The position of the gate is the state of the Turing machine. Paddles on the gate also turn the gate as the ball falls, setting the new state of the machine. The output of this box is a ball in one of ten positions, representing the combinations of five input symbols and two initial states.

The next part is the 'direction box' (green) which has levers in some of the ten paths which will alter the direction of the Turing machine later on. If a lever is hit, the machine moves left, and if not, it moves right. The actual movement isn't carried out in this phase, as the falling ball won't have nearly enough power to move the whole machine, but it sets state which will be picked up later.

After falling through the state box, the ball falls into the 'maze' (orange) which maps the ten input positions into one of five output positions, which is the output symbol for the machine. A set of gutters under the maze will return the ball to the grid in its new output symbol position.

Behind the marble alley, there's a tower which performs the movement for the whole machine. A cam (blue) drives a set of three levers (brown) which move the machine. The bottom lever can be easily deflected from one side to the other while it's raised; this is done by a linkage from the direction box. The cam drives the levers downwards, where they engage with the grid and push the whole machine forward or backward two grid spaces.

There are other cams to run the raiser and to reset the direction box each cycle.

The whole machine rides on wheels which ride on top of the grid. Using round wheels on a square grid will provide a small amount of alignment so the machine doesn't drift away from the positions of the balls.

This machine is a 5-symbol, 2-state Turing machine. The configuration comes from Stephen Wolfram's "A New Kind Of Science", which shows this to be a universal machine. While it's relatively simple, it's also ridiculously inefficient and could not be used as a practical computing device. It's just meant as a demonstration of how simple a universal computer could be.

Fab Lab success

This is a picture of two attempts at making a machine component. I'll explain what it actually does later, but this is mainly a post about how I made them.

On the right is my first attempt, cut by hand with a Dremel with a router accessory. As you can see, it's pretty rough, but it just about works - you can drop a ball bearing into one of the slots and it will roll down to one of the exit holes in the base. Sometimes they'll stick, so it needs a bit more work yet.

On the left is a CNC milled block which I was able to get made due to the opening of Fab Lab Manchester. I mentioned this a while ago when they made their press release, and they've just opened so I went along on Saturday. It's an amazing place and free to use on Fridays and Saturdays so long as you don't mind sharing the details of your project. This was cut using their enormous ShopBot CNC vertical mill.

I'd never got on well with 3D modelling programs and tended to use POVRay to model projects since I'm used to working with code rather than WYSIWYG editors. At Maker Faire UK this year I discovered OpenSCAD which is in some ways similar to POVRay - it takes a text scene description file and produces a 3D representation which can then be exported as an STL file - a format which milling machines and 3D printing machines can understand. The maze shown was just a piece of text in an editor on Thursday night, and by Saturday afternoon I'd been able to turn it into a physical object. For an amateur mechanical engineer like me, this really changes the game and allows a huge number of ideas that I'd never otherwise be able to realise. I'm very grateful to Fab Lab and especially Hayden who spent most of his afternoon showing me how to set up the mill.



If you're still interested in what it does, the diagram to the left might make it clearer. The idea is to drop a ball bearing into one of the central slots, marked by the yellow squares. The two columns represent two states of a state machine, and the five rows are the five different input symbols. Based on the state and input symbol, the ball bearing rolls down to one of five output holes. The vertical position of the output hole is the output symbol. In short, this is part of the control logic for a 5-symbol, 2-state universal Turing machine - the Wikipedia article may help explain this if you're not familiar with them.