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.

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

Slime Mold Simulates Canadian Transport System

A Crab-Based Computer

A Water Droplet-Based Computer

Knitting Is Turing Complete?

 Firefox Add-On For Local Private Translation07/06/2022Mozilla has released the Firefox Translations add-on which lets you translate websites in Firefox without using the cloud. This is the latest development of the ongoing Project Bergamot, which is buil [ ... ] + Full Story TypeScript 4.7 Adds Node.js ECMAScript Module Support06/06/2022TypeScript 4.7 has been released with improvements including ECMAScript module support in Node.js, instantiation expressions, and control-flow analysis for computed properties. + Full Story More News