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 realizations. For example, consider the following entry from legoofdoom.blogspot.com:
Or how about the following 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 the following 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 visualize 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 colored 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 realized 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)?
If you found this article to be interest, visitMicrocontroller / MCU Designline where – in addition to my blogs on all sorts of "stuff" (also check out my Max's Cool Beans blog) – you will find the latest and greatest design, technology, product, and news articles with regard to all aspects of designing and using microcontrollers.
Also, you can obtain a highlights update delivered directly to your inbox by signing up for my weekly newsletter – just Click Here to request this newsletter using the Manage Newsletters tab (if you aren't already a member you'll be asked to register, but it's free and painless so don't let that stop you [grin]).
Last but certainly not least, make sure you check out all of the discussions and other information resources at MicrocontrollerCentral.com, including blogs by yours truly.
Very strange how history repeats itself. The Turing machine is Alan Turing's mathematical proof that a programmable digital computer was possible using nothing but George Bool's logic gates, however they had to wait for Tommy Flowers to invent a working vacuum tube logic gate. In 1985, David Deutsch described a quantum Turing machine using nothing but Richard Feynman's Qbits, or in other words a mathematical proof that a programmable quantum computer was possible. Now we are waiting on someone to invent a practical quantum logic gate. Just recently, a single atom transistor has been created (http://www.purdue.edu/newsroom/research/2012/120219KlimeckAtom.html). I wonder when this article will be repeated for the, as yet to be created, quantum Turing machine.
Like in the CERN lab effort, the smaller you digging into understand subparticles, the larger the forces required (The practical size of a magnetic field generator is not limited by the size but the COST and complexity of the structure).
Likewise, I infer by your comment Max, that there is a practical limit of economics.
The cool factor can only take you so far.
David Patterson, known for his pioneering research that led to RAID, clusters and more, is part of a team at UC Berkeley that recently made its RISC-V processor architecture an open source hardware offering. We talk with Patterson and one of his colleagues behind the effort about the opportunities they see, what new kinds of designs they hope to enable and what it means for today’s commercial processor giants such as Intel, ARM and Imagination Technologies.