Spelunking CACM, Vol. 27 (1984): Robots, Elephants, Trusting Trust, and the Space Shuttle

Cartoons from three decades of Saturday Review on the topic of computers and robots were selected to present changing attitudes toward the technology. This review gives us the 1946 image at the top. Fascinating view of changing attitudes; the authors of the article assert that people began to take the topic more seriously as the machines became more real. (Of course it's no surprise that everyone in the cartoons is white and looks middle-aged and wealthy.)

Overall, this year felt like a bit of yawner, but a few things really stand out. It feels like a highly technical year, and of course the more technical a paper it is the narrower it is. I'm not sure if this is actually a change from prior years, but I came away with this impression, and a couple of these sampled papers will show why.

Leslie Valiant's "A Theory of the Learnable" is certainly considered a landmark: it has been cited over 9,000 times, according to Google Scholar. Cited in a lot of quantum machine learning (QML) papers, this is a highly technical paper with mathematical theorems and proofs showing that certain classifications can be learned in polynomial time, and I definitely don't fully understand it yet. Gotta love this image from the conclusion, though:

Consider a world containing robots and elephants. Suppose that one of the robots has discovered a recognition algorithm for elephants that can be meaningfully expressed in k-conjunctive normal form. Our Theorem A implies that this robot can communicate its algorithm to the rest of the robot population by simply exclaiming "elephant" whenever one appears.

I wonder how many elephants are required...

Speaking of landmarks, the creators of UNIX, Ken Thompson and Dennis Ritchie, received their Turing Award in 1983, and their speeches are printed here. Thompson's speech on trust is funny, engaging, insightful, and unexpected, and at least in my circle of friends probably the most-cited Turing talk of all.

A benchmark paper on, well, benchmarking appeared in October -- the original Dhrystone paper. As far as I'm aware, the first benchmark per se was Whetstone, originally written in ALGOL 60 in the very early 1970s, then rewritten in FORTRAN, which is probably its best-known form. Dhrystone came along a decade later. The paper contains full source in Ada, which was the trendy programming language of the day. Hard to imagine publishing several hundred lines of code in CACM today. The paper discusses a version in C but doesn't include it, claiming that an "equivalent" program in C is harder than an equivalent program in Pascal due to the lack of native language support for assigning (copying) data structures and strings. Benchmarking of quantum computers is a hot research topic now, so it's always nice to revisit the origins.

The Dhrystone paper cites a 1971 collection of FORTRAN programs by Donald Knuth, who is in CACM again this year analyzing the complexity of songs.

And a personal note -- my former colleague and friend Yigal Arens, talking to a UNIX computer in English. Nice.

The shining jewel of the year (besides the Thompson paper) is the September special issue on the Space Shuttle. I still teach from one or two of the papers in this issue. At the time, the Space Shuttle was considered the most complex machine ever built, and it required a sophisticated control system. IBM built the computers, and included a sophisticated fault tolerance scheme using five computers. It would be interesting, in today's context, to compare this system to the control system of SpaceX Dragon spacecraft.