Martin Davis
Engines of Logic
An excerpt
Chapter One
LEIBNIZ'S DREAM Situated southeast of the German city of Hanover, the orerich veins of the Harz mountain region had been mined since the middle of the tenth century. Because the deeper parts tended to fill with water, they could only be mined so long as pumps kept the water at bay. During the seventeenth century water wheels powered these pumps. Unfortunately, this meant that the lucrative mining operations had to shut down during the winter season when the streams were frozen. During the years 16801685, the Harz mountain mining managers were in frequent conflict with a most unlikely miner, G. W. Leibniz, then in his middle thirties. Leibniz was there to introduce windmills as an additional energy source to enable allseason operation of the mines. At this point in his life, Leibniz had already accomplished a lot. Not only had he made major discoveries in mathematics, but he had also acquired fame as a jurist and had written extensively on philosophical and theological issues. He had even undertaken a diplomatic mission to the court of Louis XIV in an attempt to convince the French Sun King of the advantages of conducting a military campaign in Egypt (instead of against Holland and German territories). Some seventy years earlier, Cervantes had written of the misadventures of a melancholy Spaniard with windmills. Unlike Don Quixote, Leibniz was incurably optimistic. To those who reacted bitterly to the evident misery in the world, Leibniz responded that God, from His omniscent view of all possible worlds, had unerringly created the best that could be constructed, that all the evil elements of our world were balanced by good in an optimal manner. But Leibniz's involvement with the Harz mountain mining project ultimately proved to be a fiasco. In his optimism, he had not forseen the natural hostility of the expert mining engineers toward a novice proposing to teach them their trade. Nor had he allowed for the inevitable breakin period a novel piece of machinery requires or for the unreliability of the winds. But his most incredible piece of optimism was with respect to what he had imagined he would be able to accomplish with the proceeds he had expected from the project. Leibniz had a vision of amazing scope and grandeur. The notation he had developed for the differential and integral calculus, the notation still used today, made it easy to do complicated calculations with little thought. It was as though the notation did the work. In Leibniz's vision, something similar could be done for the whole scope of human knowledge. He dreamt of an encyclopedic compilation, of a universal artificial mathematical language in which each facet of knowledge could be expressed, of calculational rules which would reveal all the logical interrelationships among these propositions. Finally, he dreamed of machines capable of carrying out calculations, freeing the mind for creative thought. Even with his optimism, Leibniz knew that the task of transforming this dream to reality was not something he could accomplish alone. But he did believe that a small number of capable people working together in a scientific academy could accomplish much of it in a few years. It was to fund such an academy that Leibniz had embarked on his Harz mountain project. Leibniz's Wonderful Idea Leibniz was born in Leipzig in 1646 into a Germany divided into something like 1,000 separate, semiautonomous political units and devastated by almost three decades of war. The Thirty Years War, which didn't end until 1648, was fought mainly on German soil, although all of the major European powers had participated. Leibniz's father, a professor of philosophy at the University of Leipzig, died when the child was only six. Over the opposition of his teachers, Leibniz gained access to his father's library at the age of eight and soon became a fluent reader of Latin. Destined to become one of the greatest mathematicians of all time, Leibniz got his first introduction to mathematical ideas from teachers who had no inkling of the work elsewhere in Europe that was revolutionizing mathematics. In the Germany of that day, even the elementary geometry of Euclid was an advanced subject, studied only at the university level. However, in his early teens, his school teachers did introduce Leibniz to the system of logic that Aristotle had developed two millennia earlier, and this was the subject that aroused his mathematical talent and passion. Fascinated by the Aristotelian division of concepts into fixed "categories," Leibniz thought of what he came to call his "wonderful idea": He would seek a special alphabet whose elements represented not sounds, but concepts. A language based on such an alphabet should make it possible to determine by symbolic calculation which sentences written in the language were true and what logical relationships existed among them. Leibniz remained under Aristotle's spell and held fast to this vision for the rest of his life. Indeed, for his Bachelor's degree at Leipzig, Leibniz wrote a thesis on Aristotelian metaphysics. His master's thesis at the same university dealt with the relationship between philosophy and law. Evidently attracted also to legal studies, Leibniz obtained a second bachelor's degree, this time in law, writing a thesis emphasizing the use of systematic logic in dealing with the law. Leibniz's first real contribution to mathematics developed out of his Habilitationsschrift (in Germany, a kind of second doctoral dissertation) in philosophy: As a first step toward his wonderful idea of an alphabet of concepts, Leibniz foresaw the need to be able to count the various ways of combining such concepts. This led hint to a systematic study of the problem of counting complex arrangements of basic elements, first in his Habilitationsschrift and then in his more extensive monograph Dissertatio de Arte Combinatoria. Continuing his legal studies, Leibniz presented a dissertation for a doctorate in law at the University of Leipzig. The subject, so typical for Leibniz, was the use of reason to resolve cases in law thought too difficult for resolution by the normal methods. For reasons that are not clear the Leipzig faculty refused to accept the dissertation, so Leibniz presented it instead at the University of Altdorf, near Nuremberg, where it was received with acclaim. At the age of twentyone, his formal education completed, Leibniz faced the usual problem of the newly graduated: how to develop a career. Paris Uninterested in a career as a university professor in Germany, Leibniz pursued his only real alternative: to find a wealthy noble patron. He found one in Baron Johann von Boineburg, nephew of the Elector of Mainz, who put Leibniz to the task of updating the legal system that had been based on Roman civil law. Soon Leibniz was appointed a judge at the High Court of Appeal and tried his hand at diplomatic intrigue, including an abortive attempt to influence the selection of a new king for Poland and a mission to the court of Louis XIV. The Thirty Years War had left France as the "superpower" on the European continent. Mainz, tensely situated on the banks of the Rhine, had known military occupation during the war. So, the burghers of Mainz understood very well the importance of forestalling hostile military action and, therefore, of good relations with France. It was in this context that Boineburg and Leibniz concocted the scheme to convince Louis XIV and his advisers of the great advantages of making Egypt the object of their military endeavors. The most important historical effect of this proposition—essentially the same proposition that led Napoleon to a military disaster over a century later—was that it brought Leibniz to Paris. Leibniz arrived in Paris in 1672 to press the Egyptian scheme and to help untangle some of Boineburg's financial affairs. Before the end of the year disaster struck when news came that Boineburg had died of a stroke. Although he continued to perform some services for the Boineburg family, Leibniz was left without a reliable source of income. Nevertheless he managed to remain in Paris for another four extremely productive years that included two brief visits to London. On the first of these, in 1673, he was unanimously elected to the Royal Society of London based on the model he was able to exhibit of a calculating machine capable of carrying out the four basic operations of arithmetic. Although Pascal had designed a machine that could add and subtract, Leibniz's was the first that could multiply and divide as well. This machine incorporated an ingenious gadget that became known as a "Leibniz wheel," a device common in calculating machines well into the twentieth century. About his machine, Leibniz wrote: And now that we may give final praise to the machine we may say that it will be desirable to all who are engaged in computations which, it is well known, are the managers of financial affairs, the administrators of others' estates, merchants, surveyors, geographers, navigators, astronomers ... But limiting ourselves to scientific uses, the old geometric and astronomic tables could be corrected and new ones constructed by the help of which we could measure all kinds of curves and figures ... it will pay to extend as far as possible the major Pythagorean tables; the table of squares, cubes, and other powers; and the tables of combinations, variations, and progressions of all kinds, ... Also the astronomers surely will not have to continue to exercise the patience which is required for computation.... For it is unworthy of excellent men to lose hours like slaves in the labor of calculation which could safely be relegated to anyone else if the machine were used. Leibniz's machine could only do ordinary arithmetic, but he grasped the broader significance of mechanizing calculation. In 1674 he described a machine that could solve algebraic equations. A year later, he wrote comparing logical reasoning to a mechanism, thus pointing to the goal of reducing reasoning to a kind of calculation and of ultimately building a machine capable of carrying out such calculations. A crucial event for Leibniz, then twentysix, was meeting the great Dutch scientist Christiaan Huygens, then living in Paris. The fortythreeyearold Huygens had already invented the pendulum clock and discovered the rings of Saturn. His most important contribution, the wave theory of light, was still to come. His conception—that light consists of waves like those spreading across a pond when a pebble is tossed into it—directly contradicted the great Newton's account of light as consisting of a stream of discrete bulletlike particles. Huygens gave Leibniz a reading list enabling the younger man to quickly overcome his lack of knowledge of current mathematical research. Soon Leibniz was making fundamental contributions. The explosion of mathematical research in the seventeenth century had been fueled by two crucial developments: 1. The technique of dealing with algebraic expressions (what is generally highschool algebra) had been systematized and had become essentially the powerful technique we still use today. 2. Descartes and Fermat had each shown how, by representing points by pairs of numbers, geometry could be reduced to algebra. Various mathematicians were using this new power to solve problems that would not previously have been accessible. Much of this work involved limit processes, that is, solving a problem by using approximations to the required answer that get systematically closer and closer to that answer. The idea was not to be satisfied with any particular approximation but rather to "go to the limit," to obtain an exact solution. An example that may help to clarify this concept is one of Leibniz's own early results, one of which he was quite proud: π ‹ 4  =  1   1 ‹ 3  +  1 ‹ 5    1 ‹ 7  +  1 ‹ 9    1 ‹ 11  + ···.  On the left side of the "=" is the familar number π that occurs in the formulas for the circumference and the area of a circle. On the right side is what is called an infinite series; the individual numbers alternately added and subtracted are called the terms of the series. The dots (...) mean that it continues indefinitely. The full infinite pattern consists of fractions, with 1 as numerator and the successive odd numbers as denominators, being alternately added and subtracted and is intended to be clear from the finite part shown: After subtracting 1/11, add 1/13, then subtract 1/15, and so on. But can one actually perform an infinite number of additions and subtractions? Not really. But, starting at the beginning and breaking off at any point, an approximation to a "true" answer is obtained, and that approximation gets better and better as more terms are included. In fact, the approximation can be made as accurate as one wishes by including enough terms. In the table, it is shown how this works for Leibniz's series. When including 10,000,000 terms, a value is obtained that agrees with the true value of π/4, namely 0.7853981634 ..., to 8 places. Leibniz's series is so striking because it connects the number π, and therefore the area of a circle, with the succession of odd numbers in a particularly simple way. It is an example of one kind of problem that could be solved using limit processes—that of finding areas of figures with curved boundaries. Another kind of problem susceptible to attack using limits was finding exact rates of change, such as the varying speed of a moving body. During the last months of 1675, toward the end of his stay in Paris, Leibniz made a number of conceptual and computational breakthroughs in the use of limit processes that, taken together, are called his "invention of the calculus": Table of Approximations to Leibniz's Series Number of terms
  Sum correct to 8 decimal places
 10   0.76045990  100   0.78289823  1,000   0.78514816  10,000   0.78537316  100,000   0.78539566  1,000,000   0.78539792  10,000,000   0.78539816  1. Leibniz saw that the problems of finding areas and calculating rates of change were paradigmatic in the sense that many different kinds of problems were reducible to one or the other of these two types. 2. He also perceived that the mathematical operations required in calculating the solutions to problems of these two types were in fact inverse to each other in much the same sense that the operations of addition and subtraction (or multiplication and division) are inverse to one another. Nowadays these operations are called integration and differentiation, respectively, and the fact that they are inverse is known as the "fundamental theorem of the calculus." 3. Leibniz developed an appropriate symbolism (the very notation still in use today) for these operations, ∫ for integration and d for differentiation. Finally he found the mathematical rules needed for actually carrying out the integrations and differentiations that occurred in practice. Taken together these discoveries transformed the use of limit processes from being an exotic method accessible only to a handful of specialists into a straightforward technique that could be taught in textbooks to many thousands of people. Most important for the subject of this book, Leibniz's success convinced him of the critical importance of choosing appropriate symbols and finding the rules governing their manipulation. The symbols ∫ and d did not represent meaningless sounds like the letters of a phonetic alphabet; they stood for concepts and thus provided a model for Leibniz's boyhood wonderful idea of an alphabet representing all fundamental concepts. Much has been written about the separate and entirely independent development of the calculus by Newton and by Leibniz and about the bitter accusations of plagiarism tossed back and forth across the English Channel before the foolishness of such charges was finally understood by all. It is the great superiority of Leibniz's notation that is significant for our story. A key technique used in integration (the method of "substitution") is virtually automatic in Leibniz's notation but relatively complicated in Newton's. It has even been alleged that slavish devotion to their national hero's methods caused the English followers of Newton to lag far behind their continental contemporaries in developing the mathematical perspectives that the calculus had uncovered. Like so many who have tasted the special quality of life in Paris, Leibniz wanted to remain there as long as he could. He attempted to maintain his Mainz connections while continuing to live and work in Paris. But it soon became clear that, so long as he stayed in Paris no funds from Mainz would be forthcoming. Meanwhile an offer of a position arrived from the Dukedom of Hanover, one of the multitude of principalities that made up seventeenthcentury Germany. Although Duke Johann Friedrich had some genuine interest in intellectual matters, and the offer gave some promise of financial security, Leibniz was not eager to live in Hanover. After delaying as long as he could financially afford, Leibniz accepted the offer early in 1675. In his letter of acceptance, he asked for the "freedom to pursue his own studies in arts and sciences for the benefit of mankind." He left Paris in the fall of 1676, when it became clear that no position in Paris would be forthcoming and that the Duke would accept no further delay. Leibniz was to spend the rest of his life in the service of the Dukes of Hanover. Hanover Leibniz apparently understood perfectly well that despite his request for "freedom to pursue his own studies in arts and sciences," success in his new position would require him to do things that his patron would find useful and practical. He undertook to upgrade the ducal library and proposed various ideas for improving public administration and agriculture. Soon thereafter he began promoting his illfated project to use windmills for improving the Harz Mountain mining operations. In 1680, only a year after the Harz project with Leibniz in charge had finally been approved, his position was endangered by the duke's sudden death. It now became necessary to convince the new duke, Ernst August, to continue Leibniz's position and to support the Harz Mountain project. The new duke was a "practical" man. Unlike his predecessors, he wasn't willing to spend much on the library. Leibniz soon learned not to involve Ernst August in scholarly discussions. To help cement his position, he offered to write a short history of the duke's family. Five years later, when the duke finally closed down the Harz project, Leibniz proposed a more elaborate version of the family history: if a few gaps were filled, the family tree could be traced back to the year 600. The duke evidently regarded this as a most appropriate way to employ one of the greatest thinkers of all time, nor did he stint. To pursue this effort, Leibniz received a regular salary, a personal secretary, and travel funds for searching out genealogical information. Most likely, the optimistic Leibniz hardly imagined that he would find himself chained to genealogy for the remaining three decades of his life. (Georg Ludwig, who succeeded Ernst August on his death in 1698, was especially adamant in nagging Leibniz to complete the family history.) If Leibniz had any pupils in Hanover, they were women, for he shared none of the common prejudices concerning the intellectual capabilities of the female sex. Duchess Sophie, the talented wife of Ernst August, and Leibniz had frequent conversations about philosophical matters and carried on an extensive correspondence when Leibniz was away from Hanover. She made sure also that her daughter Sophie Charlotte, who was to become Queen of Prussia, also had the benefit of Leibniz's teachings. Sophie Charlotte, not content simply to receive Leibniz's wisdom, energetically raised questions that helped Leibniz to clarify his ideas. As the contemporary Leibniz scholar Benson Mates explains: For most of Leibniz's life, these women were his principal advocates at the courts in Hanover and Berlin. Sophie Charlotte's sudden death in 1705 devastated him; it was such an obvious loss to him that he even received formal expressions of sympathy from the emissaries of foreign governments; and when Duchess Sophie ... died in 1714, his ability to obtain support for anything other than continuing the Brunswick history came to an end. The history project did provide Leibniz with an excuse to travel, and he made use of this freedom to an extent that vexed his noble patrons. Of course Leibniz took full advantage of the possibilities of developing and maintaining scholarly contacts. In Berlin he even was able to found a Society of Science, later institutionalized as an academy. His extensive correspondence continued to span the full variety of his interests. Leibniz seemed never to tire of explaining that, since God had done as well as was possible in creating the world, there must be a preestablished harmony between what existed and what was possible and that there was a sufficient reason (whether or not we could find it) for every single thing in the world. In the realm of diplomacy, Leibniz had two pet projects: to reunite the various branches of the Christian church; and to obtain for the Dukes of Hanover the succession to the British throne. But when Georg Ludwig actually did become George I of England only two years before Leibniz's death in 1716, he brusquely rejected his employee's request for permission to leave the Hanovarian backwater for London with his patron, ordering him to hurry up and finish the family history. The Universal Characteristic But what of the wonderful idea of Leibniz's youth, his grand dream to find a true alphabet of human thought and the appropriate calculational tools for manipulating these symbols? Although he had resigned himself to the fact that unaided he could never accomplish such a thing, he never lost sight of this goal, thinking and writing about it throughout his life. It was clear to him that the special characters used in arithmetic and algebra, the symbols used in chemistry and astronomy, and the symbols he himself had introduced for the differential and integral calculus, all provided a paradigm showing how crucial a truly appropriate symbolism could be. Leibniz referred to such a system of characters as a characteristic. Unlike the alphabetic symbols which had no meaning, the examples just mentioned were, for him, a real characteristic in which each symbol represented some definite idea in a natural and appropriate way. What was needed, Leibniz maintained, was a universal characteristic, a system of symbols that was not only real, but which also encompassed the full scope of human thought. In a letter explaining this to the mathematician G. F. A. L'Hospital, Leibniz wrote: "Part of the secret of" algebra "consists of the characteristic, that is to say of the art of properly using" the symbolic expressions. This care for proper use of symbols was to be the "thread of Ariadne" that would guide the scholar in creating his characteristic. As the early twentieth century logician and Leibniz scholar Louis Couturat explained: It is algebraic notation that incarnates, so to speak, the ideal of the characteristic and which is to serve as a model. It is also the example of algebra that Leibniz cites consistently to show how a system of properly chosen symbols is useful and indeed indispensible for deductive thought. Perhaps the most enthusiastic explanation of his proposed characteristic appears in his letter to Jean Galloys, with whom Leibniz had extensive correspondence: I am convinced more and more of the utility and reality of this general science, and I see that very few people have understood its extent.... This characteristic consists of a certain script or language ... that perfectly represents the relationships between our thoughts. The characters would be quite different from what has been imagined up to now. Because one has forgotten the principle that the characters of this script should serve invention and judgement as in algebra and arithmetic. This script will have great advantages; among others, there is one that seems particularly important to me. This is that it will be impossible to write, using these characters, chimerical notions (chimères) such as suggest themselves to us. An ignoramus will not be able to use it, or, in striving to do so, he himself will become erudite. In the letter just quoted, Leibniz refers to arithmetic as well as algebra as showing the importance of an appropriate symbolism. He had in mind in particular the advantage of the Arabic system of notation that we still use today, based on the digits 0 to 9, over previous systems (like the Roman numerals) for ordinary calculation. When Leibniz discovered binary notation, in which any number can be written using only the digits 0 and 1, he was particularly impressed by the simplicity of this system. He believed that it would be useful in laying bare properties of numbers that otherwise would be hidden. Although this belief turned out to be unjustifed, this interest on Leibniz's part is remarkable in the light of the importance of this binary notation in connection with modern computers. Leibniz saw his grand program as consisting of three major components. First, before the appropriate symbols could be selected, it would be necessary to create a compendium or encyclopedia encompassing the full extent of human knowledge. He maintained that once having accomplished this, it should prove feasible to select the key underlying notions and to provide appropriate symbols for each of them. Finally, the rules of deduction could then be reduced to manipulations of these symbols, that is to what Leibniz called a calculus ratiocinator, what nowadays might be called a symbolic logic. To a presentday reader, it is hardly surprising that Leibniz did not feel able to accomplish such a program on his own, especially given the constant pressure he was under to produce the family history that his patron regarded as his principal task. But even more, nowadays it is difficult to understand how Leibniz could have seriously believed that the universe we inhabit, in all of its complexity, could be reduced to a single symbolic calculus. We can only hope to begin to comprehend the matter by attempting to see the world through the eyes of Leibniz. For him nothing, absolutely nothing, about the world was in any way undetermined or accidental; everything followed a plan, clear in the mind of God, by means of which He had created the best world that could be created. Hence, all aspects of the world, natural and supernatural, were connected by links one could hope to discover by rational means. Only from this perspective can we understand how, in a famous passage, Leibniz could write of serious "men of good will" sitting around a table to solve some critical problem. After writing out the problem in Leibniz's projected language, his universal characteristic, it would be time to say "Let us calculate!" Out would come the pens and a solution would be found whose correctness would necessarily be accepted by all. Leibniz wrote with enthusiasm about the importance of producing the calculus ratiocinator, the algebra of logic, that would presumably be needed to carry out these calculations: For if praise is given to the men who have determined the number of regular solids—which is of no use, except insofar as it is pleasant to contemplate—and if it is thought to be an exercise worthy of a mathematical genius to have brought to light the more elegant properties of a conchoid or cissoid, or some other figure which rarely has any use, how much better will it be to bring under mathematical laws human reasoning, which is the most excellent and useful thing we have. Unlike the universal characteristic concerning which Leibniz wrote with such passion and conviction, but produced little in the way of specifics, he did make a number of attempts to produce a calculus ratiocinator. Part of his most polished effort in this direction is shown in the accompanying illustration. A good century and a half ahead of his time, Leibniz proposed an algebra of logic, an algebra that would specify the rules for manipulating logical concepts in the manner that ordinary algebra specifies the rules for manipulating numbers. He introduced a special new symbol ⊕ to represent the combining of quite arbitrary pluralities of terms. The idea was something like the combining of two collections of things into a single collection containing all of the items in either one. The plus sign encourages us to think of this operation as being like ordinary addition, but the circle around it warns us that it is not exactly like ordinary addition because it is not numbers being added. Some of his algebraic rules are also found in high school algebra textbooks: to some extent the same rules work for logical concepts as for numbers. But there's more to the story. There are also rules that are very different from those for numbers. The most striking rule of this latter kind, one that in a somewhat different context George Boole was to make the cornerstone of his algebra of logic, is Leibniz's Axiom 2, A ⊕ A = A, which expresses the fact that combining a plurality of terms with itself will yield nothing new: evidently, combining all the things belonging to a given collection with that same collection of things will just produce that same collection, all over again. Of course addition of numbers is quite different: 2 + 2 = 4, not 2. Sample from One of Leibniz's Logical Calculi DEFINITION 3. A is in L, or L contains A, is the same as to say that L can be made to coincide with a plurality of terms taken together of which A is one. B ⊕ N = L signifies that B is in L and that B and N together compose or constitute L. The same thing holds for a larger number of terms. AXIOM 1. B ⊕ N = N ⊕ B. POSTULATE. Any plurality of terms, as A and B, can be added to compose a single term A ⊕ B. AXIOM 2. A ⊕ A = A. PROPOSITION 5. If A is in B and A = C, then C is in B. For in the proposition A is in B the substitution of A for B gives C is in B. PROPOSITION 6. If C is in B and A = B, then C is in A. For in the proposition C is in B the substitution of A for B gives C is in A. PROPOSITION 7. A is in A. For A is in A ⊕ A (by Definition 3). Therefore (by Proposition 6) A is in A. ............................................................................................................. PROPOSITION 20 If A is in M and B is in N, then A ⊕ B is in M ⊕ N. In the next chapter, we will see how George Boole, presumably ignorant of Leibniz's efforts, produced a serviceable symbolic logic along the lines that Leibniz had pioneered. Boole's logic subsumed the logic Aristotle had introduced two thousand years earlier, but it was only with the work of Gottlob Frege well into the nineteenth century that the serious limitations shared by the logical systems of Aristotle and of Boole were really overcome. Despite Leibniz's voluminous correspondence, we have little idea of what he was like as a person. One biographer claims to see in the few portraits of Leibniz we possess the image of a tired, unhappy, pessimistic man, in contradiction to his optimistic philosophy. Others have remarked that he liked to give cakes to his neighbors' children. Apparently, he proposed marriage when he was fifty, but thought better of it when the lady hesitated. We have the picture of Leibniz spending long days and often entire nights seated at his desk managing his enormous correspondence with remarkable punctuality, his meals brought to him from an inn by his servants. What is clear is that he was indefatigable in his work. What if Leibniz had not been shackled to his patrons' family history and been free to devote more time to his calculus rationcinator? Might he not have accomplished what Boole was only to do so much later? But of course, such speculation is useless. What Leibniz has left us is his dream, but even this dream can fill us with admiration for the power of human speculative thought and serve as a yardstick for judging later developments.
Copyright © 2000 Martin Davis. All rights reserved.

