原创 Treasure chest of tasty Turing machines

With regard to my previous blog "Check these out: 1bit processor and an ultra-cool Turing Machine", I've been bouncing around the Internet discovering all sorts of cool things...

But before we hurl ourselves headfirst into the fray with gusto and abandon, let's make sure that we're all tap-dancing to the same drum beat by briefly remind ourselves as to just what a Turing machine is when it's at home. According to the Wikipedia:

A Turing machine is a device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

The "Turing" machine was described by Alan Turing in 1936, who called it an "a(utomatic)-machine". The Turing machine is not intended as a practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.

The bottom line is that a Turing machine is something that uses very, very simple rules to perform computations. As originally conceived, Turing machines are not physical objects but mathematical ones. Having said this, lots of folks have constructed some jolly interesting physical realisations. For example, consider this entry from legoofdoom.blogspot.com.

Or how about this offering, which is described as "A mechanical Turing machine built from scrap metal." I must admit that this little rascal does have a certain "agricultural charm" (grin).

However, the tastiest one I've seen thus far was created by a guy called Mike Davey. Since Mike could not find the infinitely long tape required for the project (as specified by Alan Turing), his solution was to use 1,000 feet of white 35mm film leader and a dry erase marker. As you will see in this video, the result is absolutely incredible.

Although Mike's Turing machine is controlled by a Parallax Propeller microcontroller, this little scamp is emulating the actions of the theoretical Turing engine (sometimes the convolutions involved in all of this really make your head spin).

Now, even though I really, REALLY like Mike's solution, I must admit that I'm still drawn to the idea of a physical engine moving back and forth along tracks. We could increase the length of the track by implementing some sort of serpentine arrangement as illustrated below.

Top-down (bird's eye) view of model railway track

I'm imagining a mechanical engine something like the Lego implementation shown at the beginning of this column, but maybe moving a bit faster, trundling back and forth along this track reading and writing "something". Based on the fact that I'm always saying "Cool Beans", someone suggested that my Turing machine operates by moving beans around ... I like it!

I can really visualise something like one of these this on a table in my office trundling along performing some humongous calculation that will take years to complete... we could chart it's progress against a simulation running on a PC.

Alternatively, instead of restricting ourselves to a 1D environment, like a tape or a train track, in which our Turing machine can move only in the Forward and Backward directions, how about a 2D environment like a large chess / checkers board? In this case, our Turing machine could move Forward, Backward, Left, or Right.

Or here's another suggestion – imagine a 3D structure formed from miniature scaffolding presented in a cubic arrangement. Now imagine a Turing machine that can climb through the structure and move Forward, Backward, Left, Right, Up, and Down. In addition to clambering around, there would have to be some way for the machine to read / write data into each cube (maybe using coloured beans that it hangs from the scaffolding). My initial thought was that the machine would have to be battery-powered, which would mean it would have to come out of the framework occasionally to recharge itself. But after a moment's reflection I realised that we could use the framework itself to provide power. Just imagine how awesome this would look beavering away in the corner of my office.

OK, I've done the hard part conceiving this little beauty. All that is left is to design and build it ... any volunteers (grin)?