COMPUTING SCIENCE
Trains of Thought
Computing with locomotives and box cars takes a one-track mind
Brian Hayes
Guided by an unseen hand, a grimy railroad tank car negotiates a
series of switch points in the tracks, veering right, then right
again, then left. Next comes a lime-green box car, which makes two
lefts. I observe these events from the control tower of a railroad
facility called a hump yard, where freight cars sort themselves into
trains bound for various destinations. It is an eerie scene. The
cars glide silently downhill through the maze of tracks, seeming to
steer themselves, as if each car knows just where it wants to go.
This is an illusion; a computer two floors below me is making all
the decisions, setting the switches a moment before each car
arrives. But I can't shake the impression that the hump yard itself
is a kind of computer—that the railroad cars are executing
some secret algorithm.
It's not such a far-fetched notion. In 1994 Adam Chalcraft and
Michael Greene, who were then at the University of Cambridge, and
later Maurice Margenstern of the University of Metz, designed
railroad layouts that simulate the operation of a computer. The
machine is programmed by setting switch points in a specific initial
pattern; then a locomotive running over the tracks resets some of
the switches as it passes; the result of the computation is read
from the final configuration of the switches.
These constructions are wonderfully ingenious, although admittedly
they have little to do with the day-to-day running of real
railroads. Even at a more practical level, though, brawny steel
rails and brainy silicon chips have surprisingly rich connections.
The work of the hump yard is a case in point. Algorithms for sorting
are a specialty of computer science, but railroads were sorting
freight cars decades before the first electronic computer was built.
Methods invented by rail workers have served as metaphor and
inspiration for the development of algorithms and data structures in
computer science; conversely, the theoretical analysis of algorithms
has suggested ways for railroads to improve their operations.
» Post Comment