| A Turing Machine In LEGO |
| Sunday, 06 October 2024 | |||
|
A Turing Machine is one of those abstract ideas that is much easier to undertand if you can see it working. Now there's a proposal on the LEGO Ideas site for a Working Turing Machine. Lend it your support and it might become a commercial kit. Now that's something I would build.
According to Bananaman: The model has 4 (2²) possible symbols and 8 (2³) possible states, so in total 32 possible symbol-state combinations. Each instruction has 7 bits (3 for the state, 2 for the symbol, 1 for moving left/right and 1 for stopping), so the "source code" takes 7*32 = 224 bits or 14 bytes. That means you can make 2^224 ≈ 2.69*10⁶⁷ programs!(most of them will be useless though). The mechanism is also quite complex for a Lego set. It connects all the functions to 1 input, so that the model requires no electric motor. You can see how it works in the video.
Click on the pic to go to the page where you find the video Bananaman also addresses a potential problem for a kit - the number of components, ~2900 parts, is close to Lego IDEAS' limit of 3000 parts justifying the number by explaining that a lot of them are functional (i.e. part of the mechanism) or used to make the framework more sturdy because the mechanism is very precise and needs good support. On other other hand he lists the following plus points:
If you'd like to upvote this project you'll need to sign up to the LEGO Ideas site. Meanwhile if you want to "play" with a Turing Machine, the Google Doodle that was created to celebrate Alan Turing's 100th birthday is still available in a live playable form at the Doodle Archive. So what is a Turing Machine and why is it important? In a nutshell it is one example of the absolute minimum you need to do computation. What is more, a Turing machine is the simplest mechanism you can construct that can compute anything that can be computed. It is a theoretical construct in the sense that there are many ways of creating such a minimal universal computer, but the mechanical Turing machine is close to Turing's original conception. If you want to know more, see What is a Turing Machine? or read an even more detailed account in The Programmer’s Guide To Theory my book which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way.
More InformationLEGO Ideas - Working Turing Machine Related ArticlesGoogle Doodle - A Turing Machine Puzzle - Update: Play it Now Celebrate Charles Babbage's Birthday With LEGO To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin. 
Comments
or email your comment to: comments@i-programmer.info |
|||
| Last Updated ( Sunday, 06 October 2024 ) |
The idea for a kit for a working Turing Machine comes from Bananaman. He only posted it three weeks ago but already it has attracted 4807 supporters and is flagged as a Staff Pick. The target for being considered as a viable commercial proposition is 10,000 supporters. 
