Reviews elsewhere on the web:
plus.maths.org
Mathematical Association of America

David Harel

Computers Ltd. What they Really can't do

Computational complexity, that is the study of the resources needed to solve problems by computer, is a central part of computer science. Unofortunately this area may seem difficult to understand, despite the fact that many people have a good working knowlegde of computers. The inclusion of the P v NP question as one of the Millennium problems in mathematics may draw attention to the subject, but doesn't make it look any easier. In this book David Harel provides a short account of the subject in a way that can be understood by the non-specialist reader. It's an enjoyable read, and I would recommend it to anyone who wants a better understanding of just what the limitations of computers are.

After a general introduction to the subject the book gets on to tthe impossibility of some tasks, such as writing a general program to predict whether or not other computer programs will run forever. This is followed gy a look at problems for which the best algorithms take a time exponential in the size of the input and so are impractical for realistic use. Harel then gets on to NP complete problems, explaining why the question of whether these might have a polynomial time solution is so important. The remainder of the book shows why things might not be as bad as they seem. There's a chapter on possible ways of approaching intractable problems, such as Monte Carlo algorithms followed by a look at how intractability can be used to our benefit by allowing secure methods of communication. The last chapter considers whether artificial intelligence will ever reach the level of human abilities. The one criticism I would have of the book is in the suggestions for further reading. These are given as footnotes in the text,mixed in with references to academic paper , making it hard to follow them up - I would rather see a list at the end of the book.

Amazon.com info
Paperback 240 pages  
ISBN: 0198604424
Salesrank: 1612053
Published: 2003 Oxford University Press
Amazon price $25.00
Marketplace:New from $8.77:Used from $1.99
Buy from Amazon.com
Amazon.co.uk info
Paperback 240 pages  
ISBN: 0198604424
Salesrank: 1020109
Weight:0.7 lbs
Published: 2003 OUP Oxford
Amazon price £18.67
Marketplace:New from £13.39:Used from £1.95
Buy from Amazon.co.uk
Amazon.ca info
Paperback 240 pages  
ISBN: 0198604424
Salesrank: 3539124
Weight:0.7 lbs
Published: 2003 Oxford University Press
Marketplace:New from CDN$ 44.86:Used from CDN$ 0.73
Buy from Amazon.ca





Product Description
The computer has been hailed as the greatest innovation of the 20th century, and there is no denying that these technological marvels have dramatically changed our everyday lives. They can fly airplanes and spaceships, route millions of phone calls simultaneously, and play chess with the world's greatest players. But how limitless is the future for the computer? Will computers one day be truly intelligent, make medical diagnoses, run companies, compose music, and fall in love?
In Computers Ltd., David Harel, the best-selling author of Algorithmics, illuminates one of the most fundamental yet under-reported facets of computers--their inherent limitations. Looking only at the bad news that is proven, discussing limitations that no amounts of hardware, software, talent, or resources can overcome, the book presents a disturbing and provocative view of computing at the start of the 21st century. Harel takes us on a fascinating tour that touches on everything from tiling problems and monkey puzzles to Monte Carlo algorithms and quantum computing, showing just how far from perfect computers are, while shattering some of the many claims made for these machines. He concludes that though we may strive for bigger and better things in computing, we need to be realistic: computers are not omnipotent--far from it. Their limits are real and here to stay.
Based on hard facts, mathematically proven and indisputable, Computers Ltd. offers a vividly written and often amusing look at the shape of the future.