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

Grow Your Own Wiring

Slime Mold Simulates Canadian Transport System

A Crab-Based Computer

A Water Droplet-Based Computer

Knitting Is Turing Complete?

 Apache Drill 1.19 Milestone Release Adds Cassandra Connector09/09/2021Apache Drill has been updated in what the developers are calling its biggest release ever. Version 1.19 adds new connectors for Apache Cassandra, Elasticsearch, and Splunk, along with Avro support for [ ... ] + Full Story Amazon Releases MemoryDB For Redis02/09/2021Amazon has released Amazon MemoryDB for Redis, a new Redis-compatible, durable, in-memory database. Amazon says MemoryDB makes it easy and cost-effective to build applications that require microsecond [ ... ] + Full Story More News