This month's topics:
Computing with locomotives
"Trains of thought" is a piece by Brian Hayes in the March-April 2007 American Scientist (available online). He takes us to a "hump yard," where boxcars are sorted into trains by rolling through a series of switches: "... 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." In fact any algorithm can be so executed. In 1994 Adam Chalcraft and Michael Greene, then Cambridge undergraduates, showed how to use a track layout to implement a given Turing machine (paper available online). As Hayes explains it: "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." One of the trickier parts is what they call a distributor: it routes trains alternatively onto track 0 and onto track 1. They prove that this cannot be accomplished with a finite configuration, and exhibit the following open-ended layout to do the distribution.
Chalcraft and Greene's Distributor has two kinds of switches: spring switches which always direct an incoming car to the green track, and lazy switches which are reset by the last train through. The red arrow shows the current setting of each lazy switch. The first train through resets the leftmost lazy switch to "up" on its second pass and exits on track 1.
Train-track layouts turn out to have fascinated puzzle makers and computer scientists for quite some time. Hayes' illustrations include one of Sam Loyd's puzzles and Donald Knuth's "railroading interpretations of three important data structures: the stack, the queue and the double-ended queue, or deque." Hayes even gives us a puzzle of his own:
"The task is simply to deliver cars 1, 2 and 3 to destinations A , B and C. The cars are already in delivery order." The solution is given at the bottom of this column.
Chalcraft and Greene's work was picked up by Ian Stewart for his Mathematical Recreations column in the September 1994 Scientific American. That column ("A Subway Named Turing") is available online.Mathematical tools needed
Jeffrey Mervis contributed a "NewsFocus" piece to Science for March 16, 2007. The headline is "U.S. Math Tests Don't Line Up," and the story is that the scores in tests administered in the National Assessment of Educational Progress (NAEP) in 2005 "cannot be compared to the 1996 and 2000 assessments." Too many changes: "The 2005 test contained more algebra and less numeracy, it used a different format, and students were allowed to bring their own calculators rather than use ones provided at the test site." The NAEP is a very high-profile study; as Mervis reports, the Bush administration terms it "the nation's report card." Nevertheless no bridging study was made to set up a framework for comparing scores. Mervis gives us the sorry details: the National Assessment Governing Board (NAGB), which sets policies for NAEP, blames funding decisions by NCES (the Department of Education's National Center for Education Statistics, which runs the program). The NCES people say that "NAGB said it would not be appropriate." An outside consulting firm, analyzing what the tests had in common (about 60-65%), concluded that in fact there might have been slight gains since 2000. But the overall picture remains dismal: "the 2005 NAEP test found that a staggering 39% of U.S. high school seniors lack even a basic understanding of high school mathematics. That's up from 35% in the 2000 test and 31% in 1996." And "the large achievement gap by race and ethnicity" has widened further.
Brian Hayes' railroad puzzle and its solution. He remarks: "The procedure shown requires six reversals, three couplings and six uncouplings, for a total of 15 steps. Is there a better solution? Would some other initial permutation of the cars be more efficient? Is there a worse permutation?"
Comments: Email Webmaster