The Universal Computer

The Road from Leibniz to Turing, Third Edition

Martin Davis

• Publisher: CRC Press
• Year: 2018
• ISBN:
  9781351384810
• Edition: 3
• Topic: Matematica
• Subtopic: Matematica generale

The breathtakingly rapid pace of change in computing makes it easy to overlook the pioneers who began it all. The Universal Computer: The Road from Leibniz to Turing explores the fascinating lives, ideas, and discoveries of seven remarkable mathematicians. It tells the stories of the unsung heroes of the computer age – the logicians.

CHAPTER 1

Leibniz’s Dream

Situated southeast of the German city of Hanover, the ore-rich 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 cold mountain winter season when the streams were frozen.

During the years 1680–1685, the Harz mountain mining managers were in frequent conflict with a most unlikely miner. G. W. Leibniz, then in his middle thirties, was there to introduce windmills as an additional energy source to enable all-season 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, 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 70 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 widespread misery in the world, Leibniz responded that God, from His omniscient 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 foreseen the natural hostility of the expert mining engineers towards a novice proposing to teach them their trade. Nor had he allowed for the inevitable break-in 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.

GOTTFRIED WILHELM LEIBNIZ

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 the design in a few years. It was to fund such an academy that Leibniz 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.

Leibniz, destined to become one of the greatest mathematicians of all time, got his first introduction to mathematical ideas from teachers who had no inkling of the exciting 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 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 also at Leipzig: As a first step towards 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 him 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 21, his formal education completed, Leibniz faced the common problem of the newly graduated: how to develop a career.

Paris

Not being interested in a career as a university professor in Germany, Leibniz pursued his only real alternative: to find a wealthy noble patron. Baron Johann von Boineburg, nephew of the Elector of Mainz, was quite willing to play this role. In Mainz, Leibniz worked on a project to update the legal system based on Roman civil law, was appointed a judge at the High Court of Appeal, and tried his hand at diplomatic intrigue. This last included 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, 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, already mentioned, 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: the 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 visit in 1673, he was unanimously elected to the Royal Society of London based on his model 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.* Leibniz’s machine incorporated an ingenious gadget that became known as a “Leibniz wheel.” Calculating machines continued to be built incorporating this device 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.⁴

The machine Leibniz was “praising” was limited to ordinary arithmetic. But Leibniz 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 26, was meeting the great Dutch scientist Christiaan Huygens then living in Paris. The 43-year-old Huygens had already invented the pendulum clock and discovered the rings of Saturn. What was perhaps to be his most important contribution, the wave theory of light, was still to come. His conception—that light was fundamentally to be viewed like the waves 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 bullet-like 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 called “high-school algebra”) had been systematized and became essentially the powerful technique we still use today.

2. Descartes and Fermat had 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 what nowadays are called limit processes. Using...