Logic in the Limelight

In “Engines of Logic” Martin Davis argues that logicians played an important role in the development of the computer in the 1940’s. This book could be construed as a typical emanation from a cloistered academic trying for some exposure, on the basis of the syllogismoid

        Logicians were essential in the birth of the computer
        Computers are important
Ergo -----------------------------
        Logicians are important

After a distinguished career of publishing specialist writings in mathematical logic, Davis wrote a book aimed at the non-specialist intellectual. It was published in 2001 and has, at the time of writing, an Amazon sales rank of around 400,000. Though this probably represents a considerable decline from peak sales, it unlikely to ever have hit 1199, which is, at the time of writing, the ranking of “Logicomix” by Apostolos Doxiadis,  Christos Papadimitriou,  Alecos Papadatos, and Annie di Donna. “Logicomix” also claims that logicians played an essential role in the development of computers. Here I will be reviewing these books and I will consider the implications of their claim.

While “Engines of Logic” looks like, feels like, and sounds like many worthy similar popular books on other scientific topics (“Fermat’s Last Theorem”, “The Man Who Only Loved Numbers”, “Chaos”, …), “Logicomix” is a different kind of animal altogether. It does not explain any of the scientific substance of the topics treated. Instead it is about the human drama and emotions, of which there is plenty:

• Bertrand Russell as a child battered emotionally by an unloving grandmother. (Isaac Newton grew up in similar circumstances; while far from infallible as a recipe for genius, the treatment does seem to help.)
• Russell’s letter pointing out the inconsistency of Frege’s logical system arriving just as the printing of the book was about to start.
• An unusually high incidence of insanity, both inside and outside mental institutions.
• And mathematics, thus far the one source of unassailable certainty, becoming increasingly beset by doubts.

“Logicomix” is not part of the wave of comic books that has washed over book stores by way of Larry Gonick (statistics, physics, chemistry, genetics, cosmology, by the looks of one of the titles). I only have inside knowledge of the one on genetics, which is the opposite of “Logicomix” in both substance and form. The substance is a surprisingly accurate précis of the science. Surprising because of the scruffy style of the graphics. As I remarked, “Logicomix” does not clutter up the story with any science. In this respect the book follows Bernard Shaw, who knew better than to burden his plays with all the philosophy, critical theory, and politics he wanted to unload. Instead, he put it all in prefaces, which came out longer than the plays themselves (“Androcles and the Lion”, “Back to Methusaleh”, “Man and Superman”, “Major Barbara”, and probably others). “Logicomix” follows the same strategy, except that the factual material comes after the story.

The best of “Logicomix” is the gorgeous graphics. Only those who know, and are smitten with, the great Tintin books by Hergé (“Tintin and the Picaros”, “Tintin in Tibet”, “The Castafiore Emerald”) will know what I mean. “Logicomix” does not just emulate Hergé, but it takes the genre to new heights.

I mention “Logicomix” here because of its popular success and because it agrees with “Engines of Logic” in claiming the importance of logicians in the genesis of computers. For all the artistic merits of “Logicomix”, it is better to examine the merits of the claim on the basis of Davis’s “Engines of Logic”. Davis sees three designs as the milestones in the genesis of the computer: ENIAC, EDVAC, and ACE. ENIAC demonstrated the feasibility of large-scale numerical calculations at electronic speed. It was designed by electrical engineers. Before completion of the construction of ENIAC, design was started on a successor, in time to be called EDVAC. On this new project John von Neumann was brought in as a consultant.

The expectation was a design to be reported in a document by Eckert and Mauchly, possibly jointly with von Neumann. Unexpectedly von Neumann published a design for EDVAC under his own name. The design differed strikingly from ENIAC. Instead of being decimal, the new machine was binary. Instead of separate memories for data and program, there was a single memory without demarcation between areas for program and memory. In other words, von Neumann’s design had the attributes that have become so familiar: the binary stored-program computer.

Meanwhile, back in England, Turing designed the ACE, compared to EDVAC a cleaner, even more advanced design. Thus Davis sees logicians creating the essence of the computer out of the raw material provided by the electrical engineers in the form of ENIAC.

These logicians were von Neumann and Turing. The latter is widely acknowledged as a logician due to his work on computability. But von Neumann a logician? He was, and is, known for his work on quantum mechanics, continuous geometries, game theory, and self-reproducing automata. Less known is his early career as part of Hilbert’s group, which was to develop a logical system to serve as vehicle for the Hilbert programme aiming at a provably consistent formal system for all of mathematics. When Gödel presented his incompleteness result, von Neumann was the first to see that it wrecked Hilbert’s programme. For many of those involved a traumatic experience; see “Logicomix” for a dramatic enactment of the episode. Von Neumann would later boast never to have read a logic paper since.

Yet von Neumann was at the Institute of Advanced Studies in Princeton when Turing visited there and worked on what has become known as the Turing machine, very much a stored-program machine and certainly not a decimal one. It seems likely that von Neumann, in spite of his professed abjuration of logic, was aware of the idea. It is the progression of ENIAC -> EDVAC -> ACE and the involvement of Turing and von Neumann that leads Davis to claim the computer as a contribution by logicians.

Davis only makes the claim for the hardware architecture. It would seem that there is more scope for logic in software. Yet it is hard to find any traces of logic there. Neither in the past nor in the dominant programming languages of the present time does logic play any role. Nor does logic play any role in the use of these languages to develop software. One has to root around to find any exception to this general rule.

If one does search for languages influenced by logic, one encounters some interesting peripheral software phenomena: Lisp, functional programming, logic programming, and Prolog. When McCarthy introduced Lisp in his 1960 paper, the language was already in use. A distinctive feature was, and is, the lambda expression, usually attributed to Church’s 1940 publication “The Calculi of Lambda Conversion”. This paper is classified with Turing’s work on computability rather than with logic. In fact, Church introduced the lambda calculus in the early 1930s as part of a formal system for predicate logic. The role of the lambda calculus in that work was to make precise the scoping rules of the quantifiers. Church’s system suffered the same fate as Frege’s: soon after publication it was shown to be inconsistent. Church salvaged part of that work by separating the lambda calculus and studying it in its own right as a computational mechanism. Such are the origins in logic of the lambda expressions that are the distinctive feature of Lisp and related programming languages.

McCarthy’s presence in the Algol-60 committee may have helped to adopt the scope rules of the lambda caculus. Landin, in his paper with the sarcastic title “The Next 700 Programming Languages” rubbed in the message that you can’t really get away from the lambda calculus.

The role of the lambda calculus in programming languages was an indirect influence of logic. A more direct one was to follow. With the advent of machines performing a million of operations per second with deadly accuracy interest revived in Leibniz’s dream of a formal logical calculus that would be applicable to all areas of human thought. Disputants on a point of law or theology would sit down to their slates and say “Calculemus”, “let us calculate”.

Whatever the likelihood, or even possibility, of Leibniz’s vision, steps in this direction are interesting. Whitehead and Russell’s formalization of predicate logic may in time be seen as the first such step. In the early days of computers, the complexity of the symbolic processing required for the implementation of logical inference rules was a formidable obstacle. This obstacle was removed by J.A. Robinson’s discovery of the much simpler resolution inference rule. Part of the simplicity derived from the clausal form of first-order predicate logic, then recently introduced.

Now that logical theories were no longer too complex to program, it turned out that the programs had a forbidding computational complexity. Years were spent in removing redundancies from the resolution inference rule. One of the results of this was SLD resolution, which supports Kowalski’s procedural interpretation of logic. This led to logic programming and, roughly, the Prolog programming language of A. Colmerauer and P. Roussel. This rapidly gained a following during the late 1970s and early 1980. It was chosen as the vehicle for the Fifth Generation Computer Systems project. When that project failed, logic programming suffered a set-back from which it has not, to date, recovered.

Functional and logic programming survive as faintly glowing remains of a fire that once burned more brightly. In this situation it is interesting to read Paul Graham on the future of Lisp.

It’s worth understanding what McCarthy discovered, not just as a landmark in the history of computers, but as a model of what programming is tending to become in our own time. It seems to me that there have been two really clean, consistent models of programming so far: the C model and the Lisp model.
As computers have become more powerful, the new languages being developed have been moving steadily toward the Lisp model. A popular recipe for new programming languages in the past 20 years has been to take the C model of computing and add to it, piecemeal, parts taken from the Lisp model, like runtime typing and garbage collection.

Postscript June 28, 2010

There are a number of serious objections to the above essay. Here I will restrict myself to two. In the beginning I’m dismissive of the claims of Davis and of the Logicomix authors as “sheltered academics” vying for a place in the limelight on the strength of logic’s role in the invention of the computer.

As a result of other reading I have done since, I am now convinced that the invention of the essence of the computer is indeed due to a logician and that this logician is A.M. Turing. Davis’s book is perfectly clear about this, and should have been enough to convince me.

What we have come to call, through no fault of Von Neumann himself, the “Von Neumann machine”, is due to Turing. Von Neumann has always been generous in his acknowledgment of Turing’s contribution. This is clearly described by Davis in the book, which was published in 2000. The additional reading I have done since my essay consists of the equally detailed, and complementary accounts, as given by J.A. Robinson in an invited lecture (“The Role of Logic in Computer Science and Artificial Intelligence”) at the 1992 FGCS Conference and in “Logic, Computers, Turing, and Von Neumann” (“Machine Intelligence 13”, edited by K. Furukawa, D. Michie, S. Muggleton,  Oxford University Press 1994).

The other objection to the essay concerns Logicomix’s character assassination of Russell’s grandmother.  It is Logicomix that is to blame, but I am to blame also for my ignorance of the facts in passing on the view of Logicomix in a flippant remark. It is doubtful whether there exists a more authoritative account of her than Russell’s in his autobiography, pages 17-18:

After I reached the age of fourteen, my grandmother’s intellectual limitations became trying to me, and her Puritan mentality began to seem to me to be excessive; but while I was a child her great affection for me, and her intense care for my welfare, made me love her and gave me that feeling of safety that children need.

The Logicomix authors acknowledge that they altered facts in their dramatization of history. They mention as example that they have no evidence of Russell having visited Frege. But the account of Russell’s childhood is another level of dramatization altogether. Logicomix is like The Movie, and history is like The Book, and everybody is supposed to know that if you want to know what’s in The Book, then you have to read The Book.