The Development of Computer Assisted Mathematics

views updated

The Development of Computer Assisted Mathematics

Overview

The development of programmable electronic computers placed a powerful new tool in the hands of mathematicians. The computer's ability to manipulate symbols allows it to perform the same sort of rearrangements used by humans to solve equations. Early artificial intelligence programs were able to discover simple proofs in symbolic logic and geometry, and to solve some problems in calculus. In 1976 two University of Illinois mathematicians announced the computer-assisted proof of the famous conjecture that any map drawn on a sheet of paper could be colored with just four colors. This particular result, which required calculations more extensive than could be checked within a human mathematician's lifetime, raised a number of important questions about the nature and role of proof in mathematics.

Background

The first electronic computers were number "crunchers." Built during the Second World War and the years immediately following, they were built to find approximate numerical solutions to the complex equations that described the behavior of explosives, high performance aircraft, and the weather. In these applications, they differed from the adding machines used by accountants, mainly by being able to store many numerical quantities in different locations, and to follow a program, a set of instructions, that indicated which arithmetic operations were to be performed and in which order.

British mathematician Alan Turing (1912-1954) had developed the basic theory of the programmable computer in the 1930s. Based on an analysis of the way humans did computations, Turing described a universal symbol-processing machine that could be realized using electronic components. The components available at first were rather bulky. One of the first computers, the ENIAC, built at the University of Pennsylvania using vacuum tubes, weighed 30 tons and occupied 16,200 cubic feet. It could perform about 5,000 additions per second.

By the 1950s a number of pioneering computer scientists, Alan Turing among them, were seriously exploring the possibility that computers could display intelligent behavior. The symbol rearrangement capability of the computer was used to find simple proofs in symbolic logic and to search for theorems in plane geometry. Programs were also written to solve some problems using the calculus. Overall, however, the development of such applications proceeded slowly.

In 1976 the majority of mathematicians regarded computers primarily as a labor saving device. Many were caught by surprise when two mathematicians at the University of Illinois, Kenneth Appel (1932- )and Wolfgang Haken (1928- ), announced that they had found a proof of a long-standing conjecture, that all maps drawn in the plane can be colored using only four colors. This issue was first raised in 1852 by an Englishman, Frederick Guthrie, who noticed that he could color the counties on a map of England using only four colors and wondered if the same would be true of maps in general. The problem came to the attention of the great British mathematician Augustus DeMorgan (1806-1871) through Guthrie's younger brother, who was one of DeMorgan's students. DeMorgan quickly determined that the problem could not be easily solved and encouraged other mathematicians to look at the problem.

To prove that the four-color conjecture was in fact true, Haken and Appel first demonstrated that all possible maps consistent with some very simple rules could be classified as one of 1,936 possible cases and then used the computer to verify that each of the possible cases could be colored with four colors or less. Using one of the fastest computers available, their proof took over 1,200 hours. They had also used the computer to examine many sample cases while developing their strategy for the proof. Their published paper could only provide a sketch of the proof. The details were made available to mathematicians in a set of 400 microfiche cards, each card providing reduced-size images of dozens of computer-generated pages. Critics were quick to suggest that the proof could not be trusted. Electronic computers do make occasional errors and the fact that a single mathematician could not check the steps of the proof, even in an entire human lifetime, left one unsure that the proof could be trusted. The fact that the proof could be repeated on different computers afforded some confidence in the result, however. The search for a far simpler proof is still going on, even though mathematics affords no guarantee that even a simple true statement like the four-color conjecture will have a simple proof.

Over the second half of the twentieth century, the replacement of vacuum tubes by transistors and then by microprocessors allowed a phenomenal reduction of size and cost, while computational speed and memory increased many times. By 1990 the owner of an inexpensive desk-top computer would have the equivalent of numerous ENIACs at his or her disposal. Over the same time period a number of advances in software and output devices made it possible for people who were not computer specialists to input information into the computer and to understand the results of extensive computations. By the 1960s computer languages like ALGOL and FORTRAN allowed mathematicians to specify the operations to be performed in a manner similar to that used in writing equations on paper. Graphical output devices allowed them to see the results plotted as graphs or as solid objects viewed in perspective. In the 1970s and 1980s computer applications like spreadsheet software, made it possible to do extensive calculations and visualization without writing a program at all.

The workaday world of mathematics was changed by the release in June 1988 of Mathematica, a computer software package designed by Stephen Wolfram (1959- ) and a group of collaborators. Mathematica could run on an inexpensive desktop computer, accepting inputs in a form very close to that used by mathematicians and then manipulating the symbols to find an exact solution when possible. Mathematica could provide approximate numerical results to any number of decimal places and could plot graphs in two-dimensional form or in three-dimensional perspective. Furthermore, Mathematica included capabilities to draw a large number of three-dimensional mathematical objects in perspective. Mathematica and a number of competing software packages are being released in updated and more powerful versions every few years.

Impact

The uneasiness felt by many mathematicians at having to accept a proof that could not be checked in any realistic amount of time has died down, but not disappeared. Gone forever, however, are the days when mathematics professors would brag about the small number of computers in their department. Instead, the computer has become not only a faithful assistant for doing the more tedious manipulation of symbols but also as a tool for discovery. A computer can, for instance, answer questions about what will happen if a mathematical operation is repeated a million times. This has lead do the discovery of a number of those mathematical objects called fractals, many of which are defined as sets of points that have a certain property when a specified operation is continued indefinitely. The study of equations that are too complex to have an exact solution has remained important for both pure and applied mathematicians.

Computer software can also perform visualization tasks is spaces of more than three dimensions. The fundamental connection between algebra and geometry was established in the seventeenth century by the French Philosopher René Descartes (1596-1650). Using Descartes's analytic geometry, mathematicians are able to describe the solution to a set of equations as a set of points in a two- or three- or higher dimensional space. Often the points form a geometrical structure: a curve, a surface, or a related structure. While humans can draw curves in two-dimensional space and make models of surfaces in three-dimensional space, to understand the structure of objects in higher dimensions it is often useful to look at their "shadow" or projection in two dimensions. This is a task that is relatively easy for computers with modern display devices, and this makes it possible for a mathematician to "view" a higher dimensional object from any angle until he or she understands the structure well.

The development of computers has also served to define a number of new problems and several new areas of mathematics. The field of automata theory deals with the behavior of simple symbol processing machines that can exist in only a finite number of states. This field includes problems such as the so-called "busy-beaver" problem, which asks, for each number of states, what is the longest string of symbols that such an automaton can be made to print and then come to a stop, given a string of zeros as input. It has been found that only 13 symbols can be output by a four-state automaton, but that a five state automaton can output 4098 or more symbols before stopping.

Another mathematical field, called algorithmic complexity theory, is concerned with measuring the difficulty of mathematical tasks. It asks such questions as: What is the length of the shortest set of instructions needed to compute the digits of "pi" or the square root of two. Related to it is the field of computational complexity, which attempts to classify problems by the number of steps required to solve them. Given that computers can be expected to become faster and more powerful in the years to come, it is likely that the role played by computers in mathematics will be even more significant in the future.

DONALD R. FRANCESCHETTI