**
**

Kenneth I. Appel, who helped usher the venerable mathematical proof into the computer age, solving a longstanding problem concerning colors on a map with the help of an I.B.M. computer making billions of decisions, died on April 19 in Dover, N.H. He was 80.

The cause was esophageal cancer, which was diagnosed in October, his son Andrew said.

Since the time of Euclid and Pythagoras, proofs of mathematical theorems had consisted of long strings of equations or geometric notations that any mathematician could read and quibble with, all marching logically, step by step, toward a conclusion. But the proof that Dr. Appel and a colleague, Wolfgang Haken, established in 1976 was of a different order.

Their conclusion, that four colors would suffice for any map, depended on 1,200 hours of computer time — the equivalent of 50 days — and 10 billion logical decisions all made automatically and out of sight by the innards of an I.B.M. computer at the University of Illinois in Urbana.

Hailed in some circles, including this newspaper, as “a major intellectual feat,” the proof shepherded computers toward a greater role in higher math. But it made many mathematicians uneasy; they worried about computer bugs and wondered how they could check or understand a “proof” they could not see. And it ignited a long-running debate about what constitutes a mathematical proof.

“Like a landmark Supreme Court case, the proof’s legacy is still felt and hotly debated,” said Edward Frenkel, a mathematician at the University of California, Berkeley.

Kevin Short, a mathematician at the University of New Hampshire, where Dr. Appel spent his later years, called the feat “a watershed for modern mathematics.”

“It has spawned whole fields of study,” he said.

Kenneth Ira Appel (pronounced ah-PEL) was born on Oct. 8, 1932, in Brooklyn and grew up in Queens, where he graduated from Queens College with a degree in mathematics in 1953. His father, Irwin, was an electrical engineer, and his mother, the former Lillian Sender, had been an office worker.

After a short stint as an actuary and two years in the Army, Kenneth Appel enrolled at the University of Michigan, where he earned a Ph.D. in math in 1959. During the summers, he programmed computers for Douglas Aircraft.

Dr. Appel soon went to work for the Institute for Defense Analyses in Princeton, N.J., doing research in cryptography and number theory for the federal government. He joined the University of Illinois as a professor in 1961. Long interested in Democratic politics, he also served a term on the Urbana City Council.

Some of the thorniest problems in math are simple to state but hideously complex under the surface. Such is the case with the four-color theorem, first enunciated by an English mapmaker, Francis Guthrie, in 1852. He asserted that to create a map in which no adjacent countries are the same color, only four colors are needed. Although everyone believed it was true, proof had eluded a century of mathematicians until Dr. Appel attended a lecture in 1972 by Dr. Haken.

Because of the bewildering variety of map configurations, Dr. Haken was contemplating using computers to solve the problem, but as he related in his lecture that evening, experts had convinced him that it was not possible.

Dr. Appel, familiar with computers from his defense and government work, was more optimistic.

“I don’t know of anything involving computers that can’t be done; some things just take longer than others,” he said to Dr. Haken afterward, according to an account in the journal Social Studies of Science by Donald MacKenzie of the University of Edinburgh. “Why don’t we take a shot at it?”

The two started off by showing that the universe of all possible maps must contain what mathematicians call an “unavoidable set” of 1,936 different configurations. One configuration might be a country surrounded by four neighbors, for example.

Their task, then, was to prove that each of these configurations could be rendered on a map using only four colors in such a way that no two adjacent land areas were of the same color. That was where the heaviest computation would come in. To help, they recruited a computer science graduate student, John Koch, and Dr. Appel persuaded the university to let them use its I.B.M. 370-168 computer, newly acquired for administrative services.

Those were the days when computers filled an entire room, although their memory capacities were minuscule compared with a modern smartphone. Dr. Short recounted an occasion, as described by Dr. Appel, when the computer gave an unexpected answer.

“Oh, that wire must have fallen out again,” Dr. Appel said.

Dr. Appel began to think of the computer as a partner, though with a different kind of brain, with almost “an artificial intelligence,” he told Dr. MacKenzie.

## No comments:

## Post a Comment