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: 139291
Weight:0.31 lbs

Published: 2003 Oxford University Press, USA

Amazon price $17.95

Marketplace:New from $10.44:Used from $17.10

Buy from Amazon.com

Amazon.co.uk info

Paperback 240 pages
ISBN: 0198604424
Salesrank: 444491
Weight:0.31 lbs

Published: 2003 OUP Oxford

Amazon price £7.19

Marketplace:New from £3.57:Used from £3.57

Buy from Amazon.co.uk

Amazon.ca info

Paperback 240 pages
ISBN: 0198604424
Salesrank: 450394
Weight:0.31 lbs

Published: 2003 Oxford University Press

Marketplace:New from CDN$ 13.64:Used from CDN$ 23.02

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.

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.

Easy introduction ****
The is a good introductory book into the limits of computation. The book introduces the major concepts and vocabulary in a very easy to understand way. However that is the limit to this book on limits. If you are looking for non-technical information, then this may well be the book for you. If you are looking for proofs, answers to your homwork problems, or rigor, you will be disappointed. The author states many conjectures few have proofs. From the conjectures he uses easily understood arguments to make his points. The conjectors are in fact true, but you will have to look elsewhere to find proofs. The reasons I gave 4 stars instead of 5 are twofold. Although the book is pretty good, the writing seems a bit quirky at times. I would have liked to have seen a bit more rigor. Although I can understand wanting the book to be as simple as possible, but many of the proofs are not very difficult and could have been included (for example the halting problem).

Easy introduction ****

The is a good introductory book into the limits of computation. The book introduces the major concepts and vocabulary in a very easy to understand way. However that is the limit to this book on limits. If you are looking for non-technical information, then this may well be the book for you.

If you are looking for proofs, answers to your homwork problems, or rigor, you will be disappointed. The author states many conjectures few have proofs. From the conjectures he uses easily understood arguments to make his points. The conjectors are in fact true, but you will have to look elsewhere to find proofs.

The reasons I gave 4 stars instead of 5 are twofold. Although the book is pretty good, the writing seems a bit quirky at times. I would have liked to have seen a bit more rigor. Although I can understand wanting the book to be as simple as possible, but many of the proofs are not very difficult and could have been included (for example the halting problem).

A limited introduction to the limits of Computation ****
This another nice book from David Harel, the author of the delightful 'Algorithmics : the spirit of Computer Science', which introduces the general reader to the limits of computation (and hence the limits of what computers can do). Harel, who's a renowned figure in the field of Theoretical Computer Science, has the ability to write and explain in a way that makes things seem wonderfully clear, and indeed it is only such authors who can write good books for the general reader. This small (240 pages) book is quite ambitious in its coverage of topics - starting off with the notion of an algorithm, it goes on to discuss Efficiency and correctness, Turing machines, Finite state machines, Decidability, Computability, Complexity, NP-completeness, Recursion, Parallel algorithms, Probabilistic algorithms, and even touches upon Quantum Computing and Artificial Intelligence !! All this is done with almost no mathematics, at least hardly any beyond high-school level. The reader is gently introduced to some of the most celebrated problems of Computer Science, and he/she can get a feel of the nature of this exciting and interesting field. Throughout the book, the author keeps underscoring the fact that no matter how far technology progresses, there'll always be problems that we can't solve cheaply, or can't solve at all, or can't ever know whether they can be solved or not (!!), ie he stresses that there are problems that are 'beyond computers', which cannot be tamed by more and more processing power or any other technological advancements. This book covers pretty much the same range of topics as Harel's earlier book, 'Algorithmics : the spirit of Computer Science', but in only half the number of pages, and with a heavy emphasis on the 'limitations' of computers, which actually are limitations of our knowledge rather than of the machines themselves. How does it compare with the eariler book ? Well, it's more uptodate, since it was published in 2000, whereas the other one was in 1992 - so here you find buzzwords like 'Java', 'Dotcom', 'Quantum Computing', etc, which you wouldn't find in the earlier book, but on the whole i prefer the earlier one, since it had a little more detail, made you think a little more, and even had exercises for those who were interested in probing further. So all in all, if you want a light, breezy introduction to the basic ideas of Theoretical Computer Science which doesn't demand too much concentration, this is a good choice, but if you're willing to put in some time & effort & enjoy puzzles & logical thinking, then you'll find Harel's other book, 'Algorithmics : the spirit of Computer Science' much more rewarding.

A limited introduction to the limits of Computation ****

This another nice book from David Harel, the author of the delightful
'Algorithmics : the spirit of Computer Science', which introduces the
general reader to the limits of computation (and hence the limits of
what computers can do).

Harel, who's a renowned figure in the field of Theoretical Computer Science,
has the ability to write and explain in a way that makes things seem
wonderfully clear, and indeed it is only such authors who can write good
books for the general reader.

This small (240 pages) book is quite ambitious in its coverage of topics -
starting off with the notion of an algorithm, it goes on to discuss
Efficiency and correctness, Turing machines, Finite state machines,
Decidability, Computability, Complexity, NP-completeness, Recursion,
Parallel algorithms, Probabilistic algorithms, and even touches upon
Quantum Computing and Artificial Intelligence !!

All this is done with almost no mathematics, at least hardly any beyond
high-school level. The reader is gently introduced to some of the most
celebrated problems of Computer Science, and he/she can get a feel of
the nature of this exciting and interesting field.

Throughout the book, the author keeps underscoring the fact that no matter
how far technology progresses, there'll always be problems that we can't
solve cheaply, or can't solve at all, or can't ever know whether they
can be solved or not (!!), ie he stresses that there are problems that
are 'beyond computers', which cannot be tamed by more and more processing
power or any other technological advancements.

This book covers pretty much the same range of topics as Harel's earlier
book, 'Algorithmics : the spirit of Computer Science', but in only half
the number of pages, and with a heavy emphasis on the 'limitations' of
computers, which actually are limitations of our knowledge rather than
of the machines themselves.

How does it compare with the eariler book ? Well, it's more uptodate,
since it was published in 2000, whereas the other one was in 1992 -
so here you find buzzwords like 'Java', 'Dotcom', 'Quantum Computing',
etc, which you wouldn't find in the earlier book, but on the whole
i prefer the earlier one, since it had a little more detail, made you
think a little more, and even had exercises for those who were interested
in probing further.

So all in all, if you want a light, breezy introduction to the basic ideas
of Theoretical Computer Science which doesn't demand too much concentration,
this is a good choice, but if you're willing to put in some time & effort
& enjoy puzzles & logical thinking, then you'll find Harel's other book,
'Algorithmics : the spirit of Computer Science' much more rewarding.

Popularization At Its Best *****
This book is a masterpiece! It can be read on many levels and should be a must for anyone who knows how to read and think. The layman will get a gripping and very accessible account of the limits of computing in particular, and the boundaries of knowledge in general. The professional will be able to see, in a nutshell, and explicitly, what he or she or it already knew, but did not really FEEL. But note that this book does not put down computers, but shows the intrinsic limitation of all knowledge. It should have been subtitled: `What EVEN computers can't do'.

Popularization At Its Best *****

This book is a masterpiece! It can be read on many levels and should be a must for anyone who knows how to read and think. The layman will get a gripping and very accessible account of the limits of computing in particular, and the boundaries of knowledge in general. The professional will be able to see, in a nutshell, and explicitly, what he or she or it already knew, but did not really FEEL. But note that this book does not put down computers, but shows the intrinsic limitation of all knowledge. It should have been subtitled: `What EVEN computers can't do'.

Does the author have a vendetta against computers? ***
Does the author have a vendetta against computers or something? The first few chapters slag off computers a great deal saying they can't do this, or they can't do that. Just because you can't work out the answer for something yourself (albeit a human) doesn't mean you can pass it off as being a computer problem/ error, but put more precisely something 'They really can't do' (as the title states). Some of the points made in the book will never be solved by a human let alone a computer. But the book does make you think, and opens your mind to various other topics that you would never really bring into consideration when thinking about computers.

Does the author have a vendetta against computers? ***

Does the author have a vendetta against computers or something? The first few chapters slag off computers a great deal saying they can't do this, or they can't do that. Just because you can't work out the answer for something yourself (albeit a human) doesn't mean you can pass it off as being a computer problem/ error, but put more precisely something 'They really can't do' (as the title states). Some of the points made in the book will never be solved by a human let alone a computer.

But the book does make you think, and opens your mind to various other topics that you would never really bring into consideration when thinking about computers.

Interesting but repetitive ***
Harel presented an interesting case against computers, but he just seemed to be driving one or two points home too much. Yes, we KNOW computers are serial and that some tasks take ages. Yet it the current paradigm of computing is rapidly shifting (parallel, quantum, molecular...) and while he does briefly address these, I don't think enough emphasis is given to quite how important non-computable issues are. At the moment, cryptography is non-computable (well, not true - but very hard) and quantum computing will theoritically destroy that...etc. I don't mean to dismiss this book - it does have some very interesting points, thoughts and ideas and the title of the books obviously suggests that it should look at the BAD points of computers as opposed to the good, but a more open approach could have been taken.

Interesting but repetitive ***

Harel presented an interesting case against computers, but he just seemed to be driving one or two points home too much. Yes, we KNOW computers are serial and that some tasks take ages. Yet it the current paradigm of computing is rapidly shifting (parallel, quantum, molecular...) and while he does briefly address these, I don't think enough emphasis is given to quite how important non-computable issues are. At the moment, cryptography is non-computable (well, not true - but very hard) and quantum computing will theoritically destroy that...etc.

I don't mean to dismiss this book - it does have some very interesting points, thoughts and ideas and the title of the books obviously suggests that it should look at the BAD points of computers as opposed to the good, but a more open approach could have been taken.