|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.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Saturday, 18 August 2018 )|