Computing With Trains - Turing's Trains
Written by Mike James   
Saturday, 18 August 2018

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.



What Languages Do Devs Want to Learn?

Python, of course. What comes as a surprise is the size of the margin between Python and the rest of the pack. The other unexpected finding is that JavaScript doesn't even make it into the top 10. So, [ ... ]

An Introduction to Neo4j

Learn about Neo4j and Cypher in less than a day with a free course that  introduces you to graph databases and how to use the Cypher graph language to query and update a Neo4j database.

More News





or email your comment to:


Last Updated ( Saturday, 18 August 2018 )