"Computer Ltd: What They Really Can't Do" by David Harel, Oxford University Press, 240 pages, $27.50 [translated into Hebrew by Tamar Almog, Yedioth Ahronoth Books]

Toward the end of the 20th century, people realized how dependent they are on computers. The reason for this was the Y2K bug. Nearly all the experts explained what would happen if at a single given moment, the computers would stop functioning because someone neglected to consider that to input the date according to year, four digits (i.e., "2000") were needed and not just two ("00"). Billions of dollars were spent in the period prior to December 31, 1999 in order to adapt the computers to the new millennium.

While in retrospect everyone knows that none of the apocalyptic prophecies came true, at the same time humanity realized how much it needed computers. During that period, many had the feeling that computers can do everything and nothing was possible without them. Contributing to this feeling have been marketing efforts by computer giants like Intel, which is trying to convince us that the latest central processing unit (CPU) it has developed is faster, stronger and able to do more things than the previous processor. Or Microsoft, which inaugurates a new operating system every two years that, at least according to its claims, transforms the computer into an entity possessing astonishing capabilities that enable it to do absolutely anything you might want it to do.

This book, by Prof. David Harel of the Weizmann Institute of Science in Rehovot, who this year won the Israel Prize, is a breath of fresh air in that it comes along to shatter the basic assumption that the computer is able to do everything. The book already does this in the title: "Computers Ltd: What They Really Can't Do," which is rendered in the Hebrew translation as "The Computer is Not Omnipotent." In the seven chapters of the book, Harel tries to prove a thesis, upon which he expands, that dismisses the supposition that as computers become more powerful, the number of problems with which they will not be able to deal will decrease. Harel says that in most cases, the problem is not technological but rather theoretical; the computer is simply unable to solve some of the difficulties that we posed to it. This, he says, is the bad news.

Harel starts from the most basic building blocks in the world of mathematics, so that the reader will be sufficiently equipped to understand his arguments. Thus, for example, he explains what an algorithm is and how computer programs approach dealing with various algorithms.

By the second chapter of the book, Harel demonstrates his arguments by means of presenting a predicament that initially looks simple, called "the tiling problem": how to lay a floor with tiles, each of which is painted in four colors, without two color areas on adjacent tiles being identical. It quickly becomes clear to the reader that this is an insoluble problem. "There is no algorithm, and there never will be, for solving the tiling problem!" [page 32 - this and all further quotes are from the English edition] writes Harel, stressing that problems of this type, which are called "insoluble," are not particularly rare. Harel is familiar with the argument that a stronger computer could solve the problem and therefore he responds immediately: "Well, no, dear reader, you cannot ... you can't solve it, and neither can anyone else, no matter how rich or patient or smart" (page 34).

`Highly noncomputable'

Further on, Harel demonstrates a number of other problems that on the surface seem to be amazing, such as cases in which the mathematicians are unable to say when the program stops. It is especially amusing to discover that the mathematicians are grappling with a category called "the highly noncomputable." Apparently the addition of "highly" was born in the minds of extremely frustrated mathematicians, who were unable to show subsequently just how complicated the problem is.

Other problems with which Harel deals are those that might indeed be soluble, but the computer time that would be needed until the solution is reached is so lengthy that it in effect renders the fact of solving the problem altogether meaningless. Sometimes there is a need for a computer with so much memory that "even if each bit were the size of a proton, the whole known universe would not suffice to accommodate the machine!" (page 89). In some cases, people who are unaccustomed to building equations in everyday life will need patience to get through the somewhat complex explanations here.

Further on in the book, Harel examines a number of possibilities that could "eliminate the bad news." Thus, for example, he examines whether parallel computing could solve some of the problems that have been considered insoluble. His answer is "no." However, he does leave room for hope with respect to the solution for problems he calls "unreasonable," because of the extreme unlikelihood of existing computers being able to solve them.

Harel also touches upon other concepts that arouse hope among computer people, such as quantum computers or molecular computing. While he concurs that these are exciting fields, he is skeptical about their ability to eliminate the bad news entirely. Despite this, in Chapter 6, Harel indicates how it is possible to harness the immense complexity in many areas to our benefit, as in cases of encoding in which huge and complicated numbers in fact protect us.

The seventh and final chapter is a bit alien to the natural flow of the book. While Harel deals with explanations for the layman about the reasons computers are unable to do everything, in the final chapter he focuses on his personal opinions about the capacities of artificial intelligence and the possibility that one day it will reach a state in which it is equivalent to the level of human intelligence. In this instance, too, he is not optimistic (or pessimistic, depending on how you look at it), and he does not think that robots or computers will ever achieve the ability of human intelligence. This is all well and good, but in this case it is only Harel's opinion and time will tell whether he is right or not.

`Popular science'

In an interview in the newspaper Globes prior to the appearance of the book in Hebrew, Harel, almost in panic, tried to move away from the disturbing epithet "popular science." "I prefer to call this an `expository note.' A scientist's nightmare is to be remembered only as someone who has written popular science," he said in the interview. There is no fear that Harel will be remembered that way.

First of all, the book is one or two rungs above popular science, as it requires a certain and not inconsiderable degree of mathematical understanding. Although it does not demand five matriculation points in mathematics of the reader, the knowledge that it requires is far from trivial and sometimes it is necessary to read the sentences several times to get to the bottom of them (and even this does not always succeed). Moreover, Harel is considered to be a first-rank scientist, but he could have allowed himself to simplify his arguments a bit to bring more readers closer to the subject without fearing that his colleagues would look down on him because he elected to explain to the masses what is already so clear to scientists themselves.

It must be noted that this book, which has now come out in a Hebrew edition, is far from being new. The first edition was published back in 2000. A comparison of the two books shows that Harel and the editors of the Hebrew edition hardly updated the book at all (and if they did, we were unable to discern this), even though four years have elapsed since its first publication. It is possible that Harel considers that nothing has changed since then, at least with respect to the theoretical issues he discusses. It is possible that he is right, yet nevertheless it is a pity that the reader of Hebrew has not been given some sweetener that might have compensated him for the long and unjustified wait for the translation of the book.

However, no praise must be spared Harel, who at the height of the technological enthusiasm about computers and the Internet, chose to publish a book that could have been used as a pin to prick the expanding bubble that saw computers and their ability to calculate as the be-all and end-all.