The Steam-Powered Turing Machine

The "Steam-Powered Turing Machine" mural was painted on a stairwell wall of Sieg Hall nearly a decade ago by a dozen first-year graduate students seeking diversion on the eve of the qualifying examination. The SPTM was originally conjured up a few years before this by Professor Alan Borning. Borning was undertaking a revision of the graduate program brochure. Professor Larry "Tomorrow" Ruzzo was late with his biographical information for the brochure -- real late. In desperation, Borning threatened to provide text himself if Ruzzo failed to come through. The threat didn't work, and when the printing deadline arrived, Borning followed through -- that year's graduate brochure carried the following description of Ruzzo's research interests:

"Currently, his principal research project involves the construction and programming of a vaguely parallel computer, consisting of 32 steam-powered Turing machines installed in the basement of Sieg Hall. Of particular interest is the use of triple-expansion bypass valves, coupled to individual governors on each engine, to achieve write-synchronization of the machines. Graduate students have played an important role in the construction and operation of the engine, particularly in stoking the boilers, and advanced undergraduates are occasionally allowed to polish the brass gauges.

"Originally intended as a general computing engine, restrictions imposed by the Pollution Control and Noise Abatement Boards require that only algorithms running in polynomial time may be used. The project recently suffered another setback when one of Professor Ruzzo's graduate students slipped on a mouldering stack of ungraded homework exercises and fell under the write head of one of the machines. Now permanently embossed with a series of 1's and 0's, the student is suing to have the machine dismantled."

(In a peculiar twist, Ruzzo received a number of requests for reprints from departments of mining engineering in Eastern Europe!)