It is amazing what is Turing complete. It seems that all you need is something to implement a universal gate and you're home and dry. But trains? Duplo trains in this case, have some powerful, almost hidden, computational abilities. Are they Turing complete? Of course they are.

I have a fascination with how easy it is to find computational systems that are based on things that you might not think would have the ability to be used to create a computer.

In this case it is a Duplo trainset that does the computation with the assistance of cr31, aka Guy Walker, whose site has some really interesting things to look at and play with.

You may know that the flow of control through a program is like a railway line with points and loop backs, but it goes deeper than this. A railway points has two settings and you can think of this as representing 0 or 1. In the case of this railway layout we also have sprung points, which stay where they are unless a train approaches on the branch line when the wheels move the points so that it joins the mainline. The points then spring back to the mainline-through position. Sprung points give an extra power which makes constructing a modular layout slightly easier.

You have to see the simulations in action to understand how the points work.

Once you have the basic gates and flip-flops you can use a train to do computation.

Is a train layout Turing complete?

This question was answered in 1994 by Adam Chalcraft and Michael Greene, then Cambridge undergraduates, whose paper showed how to construct a Turing machine out of railway lines and a train.

If you would like to see what such a construction looks like then the layout below is an implementation of a 3-state busy beaver. A busy beaver Turing machine has the task of printing as many ones on its tape as possible before halting.

If you go to the cr31 site you can see it in action, but I would suggest that you look at some simpler examples before you try and understand something as big as this.

If you would like to see a circuit realized in real Duplo track then take a look at this three-bit binary counter:

So it does seem that the ability to compute is all around us. Is it any wonder that computer science and complexity theory are more important than you might expect? This is the true theory of everything.

More Information

Turing Trains

Train Sets Chalcraft and Greene

Computing with locomotives

Related Articles

The Trick Of The Mind - Turing Complete

Sliding Blocks Are Turing Complete

Stanford Engineers Build A Water Droplet Based Computer

Pulleys As Logic Gates    

Grow Your Own Wiring       

Slime Mold Simulates Canadian Transport System 

A Crab-Based Computer       

A Water Droplet-Based Computer       

Knitting Is Turing Complete?       

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

Make a Comment or View Existing Comments Using Disqus

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