When I was a kid I had a toy train set that my dad built. I loved it. It had switching points, side tracks, bridges, and little men with out-of-date railroad uniforms. I loved it so much that I wanted to be an engineer someday so I could drive a real train.
Before I found out that not all engineers drive trains I had my degree and it was too late to switch to poly sci. Of course I never have driven a train -- until today.
The train I'm talking about here is the computing train developed by Adam Chalcraft and Michael Greene. Their idea was published in Eureka in 1994, and made popular by Ian Stewart in The Magical Maze.
The train set consists of a single engine with no cars and a set of track components that are like the kind you'd get with your Lionel train set. Well, sort of at least. I don't remember having some of these with my set. Anyhow, they showed how you could make a Turing Machine out of these components, given you had enough space and time. (Not meant to compete with your basic hyperparallel superduperultracomputer.)
So one day David Wilson sent me an e-mail saying he thought it would be possible to make the train set components in WireWorld. I looked at it for a minute and thought, "Ya, you can". Then it dawned on me. This is my life's calling. I'm an engineer and now I get to drive my train. Here goes.
The basic elements in the Train Set are the train itself, three points -- the lazy point, the sprung point, and the flip-flop point, and a bridge or cross. As with digital logic more complicated devices are made by connecting basic element. Some of the compounds we'll use here are the read/write head, Exclusive Or gate, and the shift register. I'll be explaining the WireWorld implementation of the train set components and the machines I've built, including a Turing Machine Unary Multiplier, a binary counter, and a primitive polynomial counter. Wonderful explanations of the train set itself are given by Ian Stewart and Chalcraft and Greene.
A single electron represents the train. There are no cars. Within a point or a bridge, the electron splits as the specific function is performed, but a single electron leaves each component. You can tell where the train is by simply following this electron.
The train can go either direction on any piece of track.
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.
Here's what my WireWorld Lazy Point looks like. It needs to remember where to exit, so it contains a latch. The latch is a 7-tick flip-flop designed by Karl Scherer. The fact that it's 7-tick dictates the synchronization of other Lazy Points and Flip-Flop Points.
The point itself is on the left. The configuration on the right is the figure-of-eight arrangement that Ian Steward discusses, which is made up of two Lazy Points that repeatedly goes through a cycle of eight. Upper right, upper left, lower right, lower left, upper left, upper right, lower left, lower right. As Ian says, it's like a computer that can compute only the sequence 10100101, repeated forever.
The Sprung Point is the easiest of the three points to implement in WireWorld. 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.
The Flip-Flop Point gives our train real power. I didn't have one of these with my toy train set. I guess they're a little tricky to actually build. In WireWorld, however, it's not very difficult.
The train is allowed to enter only S, never E or W. It exits alternately E and W. Again notice the 7-tick latch.
Bridges, or crosses, are just the opposite of Flip-Flop Points. Easy to build in real life, a pain in WireWorld. In tick-logic crosses usually have at least one XOR, and are somewhat expensive. A lot of the time you can design around them and actually do without them. But with the train set you need lots.
The first bridge I'll show is a design by David Wilson. It's very ingenious and a devil of fun to watch, but it is quite expensive.
There are four other bridges to talk about, two of which are used in my designs. The first is a full-function synchronous bridge that is small but has the unfortunate characteristics of requiring proper phasing of inputs and needing four electrons continuously present. The one shown works with 8-tick latches.
The second design allows for four paths, W-E, N-S, E-W, and S-N. This is more function than required in any of the machines I've worked on. Bridges need be only three-path (W-E, N-S, and S-N) or only two-path (W-E and S-N). The fourth one shown, the two-path one, is the cross used in Mark Owen's computer.
The Turing Machine needs a Read/Write Head. This compound component consists of a Flip-Flop Point, a Lazy Point, a Bridge, and three Sprung Points. The data bit is flipped by having the train enter from the N and leave to the S. The data can be read by having the train enter from the W and leave to the E, either upper E if the data is a 1, or lower E if the data is a 0.
You might note that this component could be made quite a bit cheaper, for example, by eliminating one of the latches. But that would defeat the sprite of our train set. I wanted to use only the basic components - train, points, and bridges.
Ian Stewart showed how these components can be connected to produce a Turing Machine. And when you have a Turing Machine you can do any calculation you want, at least any that a computer can do. Ian gives an example of a 3-state, 2-symbol Turing Machine that does something - I haven't taken the time to figure out what.
I played around with this Turing Machine and was going to show it here, but instead decided to - gulp - do a Unary Multiplier. I had already designed and built several in regular tick logic, so the state machine was designed, debugged, and running. What is given here is a 9-state, 2-symbol unary multiplier that does 2 times 2 equals 4.
Ten Turing Cells are needed to do 2 times 2 equals 4. Each Turing cell needs nine Read/Write Heads since there are nine states. There are five state/input combinations that flip the symbol, so there are five calls to the subroutine that inverts the symbol. Five subroutine calls can be handled by four Lazy Points. Besides the Read/Write Heads and Lazy Points all that's needed are a lot of Bridges and Sprung Point to gate the train along the proper path.
A general 9-state train set Turing Machines needs lots and lots and lots of bridges to gate the cell input lines and output lines to the proper inter-cell lines. The train can travel either direction on any inter-cell line, and once inside a cell the sense of direction is lost. With the 9-state unary multiplier many of these connection are simply not used. This is because the states were designed such that direction is part of the state definition. Five of the nine states have the train going from left to right, the other four right to left.
One place I did skimp. Rather than have the train return to the station after the operation is complete it simply ceases to exit and goes to the great terminal in the sky.
First a single Turing Cell is shown. The Read/Write heads are stacked one on top of another. The top five have entry from the left, the bottom four entry from the right. In five cases the train changes direction. All the other times it enters from one direction, goes through a Read/Write Head, continues in the same direction, then exits.
Like I said, ten cells are needed to do 2 times 2 equals 4. The cells start out 1101100000 and after 30308 ticks end up at 1101101111.
I believe the train set is actually very versatile. It has been shown that it can make a Turing Machine, but it can also make more practical machines. One of the simplest is a binary counter. A set of Flip-Flop Points and a few Sprungs are all that is needed.
Another machine that the train set does nicely is a shift register. And of course, also an XOR. When you've got these, a primitive polynomial shift register can't be far behind.
A primitive polynomial determines the length of the register and the location of the XORs in the feedback. We'll use a 5th order polynomial here. g(x) = 1 + x^2 + x^5 So we need 5 latches in the shift register and a single XOR in the feedback path between the second and third latches in the string. It works best to XOR the data bit in the second latch as the train returns to the left, then just shift all the data to the right one location.
The register is initialized with 10000. It then seemingly haphazardly advances through the 31 non-zero states. After 58632 ticks it returns to 10000. And then just starts all over again.
