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 Mathematics opens the door to understanding biological phenomena? Image courtesy Janusz Kapusta, Images.com. | The image at left illustrates "Bringing cartoons to life," an essay by John J. Tyson under the "Connections" rubric in the February 22 2007 *Nature*. Abstract: "To understand cells as dynamic systems, mathematical tools are needed to fill the gap between molecular interactions and physiological consequences." Tyson, university distinguished professor of biological sciences at Virginia Tech, makes the point that "a network of interacting genes and proteins is a dynamic system evolving in space and time according to fundamental laws of reaction, diffusion and transport." He focuses on *programmed cell death* as an example of a a nonlinear system: "its molecular regulatory network is bistable (either off or on) at zero signal strength and monostable (on) for signals above the threshold." He posits a chemical feedback loop which "might generate" this kind of dynamic responses, and asks "But can we be sure our intuition is correct? ... How might the regulatory system fail? What are the most effective ways to intervene pharmaceutically to repair the cell-death pathway?" The answers, he proposes, will come from computer modeling. "The network of reactions ... can be cast into a set of kinetic [differential] equations. ... By following the arrows, a computer can simulate the temporal evolution of the control system under any specified experimental conditions." Tyson points to the existence of "a well-developed mathematical theory" with qualitative concepts such as bifurcation points, which "accord well with our intuitive notions," a theory which "forges a rigorous chain of deductions from molecular interactions to kinetic equations to vector fields to physiological consequences." He ends by predicting that in particular the uncertainties about "the molecular correlates of programmed cell death" will "be resolved largely by experiments driven by theoretical issues such as the importance of bistability, the roles of feedback and feed forward, and robustness in the face of noise." | Misaligned math tests 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. **Train track puzzle solution** 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?" Tony Phillips Stony Brook University tony at math.sunysb.edu |