The idea that there are some things that computers cannot do, will strike in many people's minds as surprising. Surely, as computers increase in speed and storage capacity, the impossible will become possible? Unfortunately not. The trouble is that even some simple-sounding problems (such as working out whether it is possible to cover an infinite plane with a given set of patterned tiles) are mathematically proven to be inherently no computable. No computer program will ever be able to solve such problems in every case. This is not a limitation of the software or hardware, but one of mathematics; aliens with computers of their own will face the same problem.

Almost as bad as no computable problems are intractable ones (such as determining whether there is a guaranteed winning strategy for an arbitrary chess position), which cannot be solved in a reasonable amount of time. Faster computers are no good for problems that will take several trillion trillion years to solve; even parallel processing, in which the work is shared out among many processing units, is no help.

A third category of troublemaker is the so-called “NP-complete” class of problems, the most famous of which is to determine the shortest route that will enable a travelling salesman to visit several cities. (Working out a school timetable is another example.) Such problems are interesting in that they occur in many real-world situations, and a solution for any one of them would work for the entire lot. They are not currently solved, but it is unclear if this is because no solution has yet been found or because none exists.

It is all, Mr Harel concludes, bad news of a fundamental kind. There is one glimmer of hope: quantum computers might someday be able to solve a few currently insoluble problems. And there is a silver lining: modern cryptography exploits the fact that some things (such as factoring large numbers) are difficult in order to provide security. There are some other things that computers can’t do, such as holding a convincing conversation—which is remarkably difficult, but in a different (and rather more arbitrary) way.