Chips make a hash of some dim sums

Although modest in size, this book is huge in intellectual scope. While much of the world is impressed by the power of computers and what they can achieve, there are fundamental limitations on computing, not only to do with physics as the size of transistors approaches that of atoms, but also with the nature of mathematics itself. It is the mathematical difficulty that David Harel considers.

Computers Ltd is essentially about the mathematical complexity of problems with respect to their solution by computer. Alan Turing could be considered the founder of this field. Despite its simplicity, his Turing machine is fundamentally computationally equivalent to all computers in use today. This equivalence helps greatly in the mathematical reasoning about what is or is not possible using a computer.

Difficult though the underlying mathematical fundamentals are, the book is written at a level requiring little knowledge of mathematics. However, one of its great merits is that Harel is a leading computer scientist who understands the mathematical issues intimately, rather than a populist with a superficial knowledge. Thus the book is authoritative, but is also notably accessible to the non-specialist.

The author leads the reader through the maze of algorithms that computers can tackle with some well-chosen examples. He also demonstrates problems that are impossible to solve algorithmically (for example, that of formal program verification). This may be because they are non-computable (or "undecidable" in mathematical parlance), but it may also be because they are intractable in practice for any example of realistic size.

The burning issue of P (polynomial) versus NP (non-deterministic polynomial) problems is well explored and explained. Some algorithms can be solved in polynomial time (and/or space), which effectively means they are normally tractable in practice, whereas others require exponential time, which means they are intractable for all but the smallest of problems (ie they do not scale up). Many problems could be solved in polynomial time if we had a magical oracle making the correct choice of path through the problem search space (NP). But the demonstration that there is a fundamental difference between P and NP problems has proved to be elusive; it is still an important open question in computer science that is being actively pursued by researchers.

Of course, humans are ingenious, and heuristic methods can help in overcoming some of the fundamental limitation in many cases. Parallelisation and randomisation can often be useful. Sometimes it is possible to reduce the probability of incorrectness to vanishingly and selectably small probabilities, which should make an approach highly acceptable in practice. Harel covers some approaches, such as neural networks; others, such as genetic algorithms, he omits, and it would have been interesting to hear his views on them, even if briefly.

The problems of computability can sometimes be turned to our advantage, especially in the field of security, which depends on the intractability of decoding encrypted data. Indeed, a fundamentally new mode of computation, such as quantum computing, could turn this field on its head. However, Harel thinks it unlikely in the near future, and I agree.

Although the glitzier sides of computing are ignored, the book is never dull and it avoids condescension as well. However, at some points, issues are left hanging, especially where a mathematical proof blocks further understanding, and I was left wanting more of Harel's excellent exposition supposing he had pushed further along the path.

There can be no doubt that the book covers an area of computer science that is hugely important in practice. Not only is the area little understood by computer scientists, it is also one of which the public is largely unaware. Harel has provided a book that is very accessible and academically credible. (There are many footnotes containing references to original papers for the specialist reader, which can safely be ignored by the more general reader.) Thus his book is one that would not look out of place as a reference in an academic paper but that also has the potential to sell widely, at least by academic computer-science standards. It could even be useful on an undergraduate course, in providing motivational material, although a more mathematical treatment would be expected on most computer-science courses. A short index is included, making the book a useful reference work.

Given Harel's unpretentious but authoritative style, this book has no serious competition. It could grace the shelves of academics in virtually any discipline, of public libraries and of general bookshops, with equal aplomb.

Jonathan Bowen is professor of computing, South Bank University.