Computers Ltd.: What They Really Can't Do

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).

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.

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'.