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.

LEGOTuring 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. 

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.

LEGOTMvideo

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: 

  • You can play with it,
  • You can make your own programs,
  • It has an interesting mechanism inside,
  • Its an implementation of a popular theoretical model.

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.

lego tmsq

 

 

More Information

LEGO Ideas - Working Turing Machine

Related Articles

What is a Turing Machine?

Google Doodle - A Turing Machine Puzzle - Update: Play it Now

Celebrate Charles Babbage's Birthday With LEGO

LEGO Difference Engine

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.

Banner


Apache Releases Tomcat 11
07/11/2024

Apache has announced the release of Tomcat 11, as well as marking the 25th anniversary of the first commit to the Apache Tomcat source code repository since becoming an ASF project.



Google Adds Premium Tier To Developer Program
29/11/2024

Google has added a premium tier to the Google Developer Program. The new tier is described as providing "a tailored suite of services to help developers throughout the learning, building and deploymen [ ... ]


More News

espbook

 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Sunday, 06 October 2024 )