[LINK] book review - Computers Ltd: What They Really Can't Do

[David Goldstein]

Hi all

I found this book review of Computers Ltd interesting. It's basically
 about the future of computers, and what they may never be able to
do. It's from The Economist.

Cheers
David


Don’t count on it
Sep 28th 2000
>From The Economist print edition 

COMPUTERS LTD: WHAT THEY REALLY CAN’T DO.

By David Harel.
Oxford University Press; 240 pages; $25 and £14.99 
  
Is that you?  

BOOKS about computers are often frighteningly dull and of interest
only to specialists in very small niches (“Learn to Write
Mission-Critical Solutions in Java in Three Days”). Alternatively,
they are hype-filled, buzzword-laden bibles of technobabble that set
out to explain to besuited managers how they can best exploit the
latest breakthrough. Neither type of book has a long shelf-life.
Thank heavens, then, for David Harel’s book on the theoretical
limitations of computers.

It is refreshing for two reasons. First, by stressing what computers
cannot do, no matter how powerful or complicated they may become in
future, Mr Harel, a mathematician at the Weizmann Institute of
Science in Israel, provides a welcome antidote to Internet hype. And
second, because he is dealing with the underlying mathematical theory
of computing, his text is blissfully free of brand-names and
buzzwords. The type of operating system, the make of microchip, the
choice of programming language, the brand of computer—all these are
of no consequence to his argument, because it applies equally to all
computers.

The idea that there are some things that computers cannot do will
strike many people 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 noncomputable. 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 noncomputable 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. The book ends with a brief look, for completeness, at some
of the 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.

Mr Harel is a nimble and thoughtful guide to some of the darkest
recesses of computer theory. His book will not appeal to everyone,
but everything theoretical in it will, almost certainly, be true a
century hence. At a time when many Internet books are out of date
before they have even been printed (leaving aside whether or not they
were accurate in the first place) the insights “Computers Ltd”
provides are of an unusually enduring and worthwhile nature.

_____________________________________________________________________________
http://clubs.yahoo.com.au - Yahoo! Clubs
- Join a club or build your own!