Chalcraft-Greene train track automaton
Adam Chalcraft and Michael Greene proposed a Turing-complete set of primitives for trains (Eureka 1994, Ian Stewart wrote about it later).
Also, Neise implemented it inside of WireWorld (see link in External resources, below.)
It's a 2D language, with a "head" that has a facing - the train is going some direction - and tracks that can be traversed in either direction. The tracks are connected in Y-shaped "points" of two kinds, lazy points and sprung points. From Neise: "The lazy point has three entry/exits, W, E, and S. If the train enters W it always exits S. If it enters E it always exits S. If it enters S it exits either W or E depending upon which of the two was entered most recently. You can rotate and reflect, giving lots more combinations of NEWS." Regarding the sprung point, also from Neise: "If the train enters W or E it exits S. If it enters S it always exits E. Again, reflections and rotations are gladly accepted. In the degenerate case where S is never entered, the point turns out to be a simple OR gate."
Chalcraft and Greene note that crossovers (four-way junctions allowing N-S and E-W travel) are possible to build out of these two components.
External resources
- A chapter dedicated to describing this automaton can be found in Ian Stewart's The Magical Maze: Seeing the World Through Mathematical Eyes, ISBN 0-4713506-5-6
- Article by the authors describing the system
- Implementation of the system in WireWorld
- Turing Trains: computational train track layouts