American Scientist

The Advent of the Algorithm: The Idea that Rules the World. David Berlinski. xviii + 345 pp. Harcourt, 2000. $28.

By coincidence, as I was strolling in the park wondering how to convey the flavor of this book, I found three gentlemen sitting on a bench discussing it. They were the trio on whom Galileo had depended to promulgate his dangerous ideas: Sagredo, Simplicio and Salvatio. Aha! By transcribing their conversation about the book, I would not only be saving myself the trouble of writing a review, but in thus presenting my own literary conceit, I would also be demonstrating something of David Berlinski's method:

SAGREDO: So, computers embody ideas developed by logicians over a period of centuries: Leibniz, Frege, Hilbert, Gödel, Church and Turing. What computers do is to carry out algorithms—that is, procedures or recipes that consist of individual steps, each of which is purely mechanical. We have learned about the lives and work of these great logicians.

SIMPLICIO: I loved Leibniz's audacious project for a "universal characteristic" that would reduce all thought to calculation. And I found it very amusing to learn about his boss, Duke Frederick, being distracted by a full bladder while Leibniz was trying to explain it.

SALVATIO: No, Simplicio! It is not always easy to distinguish the actual history from Dr. Berlinski's many fictions. The full bladder is surely fiction. Gottlob Frege's "team teaching mathematical logic" with Dr. Berlinski, "at the blackboard with the thick German chalk in his fingers," is another fiction. Frege died in 1925.

SAGREDO: I suppose the author uses this conceit to emphasize the debt that all logicians owe the man who first produced a complete set of rules for logical deduction. Do you suppose that any readers, noting such details as Berlinski's students' reaction to Frege's clothing, might take it literally?

SIMPLICIO: It embarrasses me to admit it, but I did. What about the story Berlinski heard from the writer Isaac Bashevis Singer, the demonstration of how dangerous logic could be, after Berlinski "happened to mention Gödel's well-known remark that logic was a powerful discipline"? Also fiction?

SALVATIO: This "well-known remark" is not to be found in Gödel's collected writings or in the extensive published reminiscences of him. Rather, in writing about Bertrand Russell's mathematical philosophy, Gödel expressed disappointment over how little had been accomplished as compared with Leibniz's hopes. Although there is much of great interest in this book, not everyone will be attracted by the interspersed, apparently irrelevant fictions, and I personally was upset by carelessness with the history.

SAGREDO: An example?

SALVATIO: Berlinski writes that Alonzo Church created his calculus of lambda conversion "in order to articulate his vision of effective computability" and that in 1936 Church proved the equivalence of his notion with Gödel's recursiveness. Neither statement is true. Church extracted the lambda calculus to salvage what he could from his logical system that his students Kleene and Rosser proved was self-contradictory. Only after Kleene had surprised his teacher by demonstrating the power of the formalism did Church formulate his famous thesis that the lambda calculus encompassed all computable operations. The equivalence with recursiveness was proved by Kleene, not Church.

SIMPLICIO: I enjoyed the examples of the abstract computers of Alan Turing but was astonished to learn that a Turing machine could be devised to carry out any particular algorithm.

SAGREDO: What puzzled me was our author saying that the computers we use are in some sense Turing machines. Our computers are useful because they can be programmed to carry out any algorithm, whereas each of Turing's devices executes a single algorithm.

SALVATIO: Remarkably, Berlinski failed to mention the most relevant connection. Turing devised a single machine of his type that is all-purpose, that all by itself can do anything that any Turing machine can do. It is such a machine that provided an abstract model for the computers we all use today.—Martin Davis, Courant Institute of Mathematical Sciences, New York University (emeritus); University of California, Berkeley