You are here

Computers, Ltd.: What They Really Can't Do

David Harel
Publisher: 
Oxford University Press
Publication Date: 
2000
Number of Pages: 
240
Format: 
Hardcover
Price: 
25.00
ISBN: 
978-0198505556
Category: 
General
[Reviewed by
J. Kevin Colligan
, on
10/11/2001
]

As many authors have noted, there are limits to power — and not just in the political arena. Computers Ltd. details the foundations of the theory of computation, and explores today's landscape in this field. And an open vista it is: quantum computations, artificial intelligence, massive parallelism — all these topics are ports of call, as well as others both well known (Turing tests and "P vs. NP") and exotic (zero knowledge proofs and time-memory tradeoffs). This book is The Hitchhiker's Guide to the Galaxy for computation.

The title itself is a pun: the book really is about the limits of computation, and not just the business thereof. The book requires little in the way of mathematical preparation for the reader, but the breadth of coverage of this very small book — just over 200 5" by 7" pages — requires careful attention and a good memory.

The core premise of the book is that the popular notion of ever more powerful computers leading to the advent of computers of unimaginable power able to tackle any problem — that the mind of man will develop computers of almost infinite capability — is not only false but theoretically unattainable.

It's more accurate to say that some problems are so hard, so demanding, that they outstrip the bounds imposed by our universe. Although some of us might expect such impossible problems to lurk in areas such as factoring or shortest-route problems, we probably don't expect them to arise in apparently simple puzzles and problems like the following.

  • The so-called "monkey puzzle." You've undoubtedly seen this one in game stores or even in novelty shops. The one I've seen consists of nine squares with some pattern on each side that must be matched against the neighboring square when all nine are placed in a 3x3 arrangement. There are over 95x109 arrangements to check: (32)! x 432, to be precise. [No wonder this puzzle frustrates me!] A similar 5x5 puzzle has (52)! x 452 possible arrangements. That is a big number. Really big. How big? Figure it out yourself: assume your computer could check 106 possibilities per second (including the needed bookkeeping), and see how many universe lifetimes it would take.
  • WS1S problems. Ones like determining the validity of statements like "there is a set of integers S, every one of which has the property that if you add one to it, then..." WS1S problems — in general, not a specific WS1S problem — admit no multiple exponential algorithm, for any multiple. How's that? Quoting Harel's explanation:

This means that given any algorithm that is capable of determining truth in this logic, you can pile up as many 2s as you want in a cascade of exponentials of the form 222...N, and there will still be formulas of length N that will require your algorithm to run for more than that amount of time.

Ouch.

Harel's little book covers wide ground, touching on many of the reasons why what seem to be "reasonable" fixes to accommodate these really hard problems are, in fact, not reasonable enough. The book is a tour de force that succinctly covers a field at once fascinating and yet often out of reach to those not working there.

Harel has done an excellent job of pulling together threads from today's entire tapestry of computation, and in fact has given the reader a glimpse of the many patterns present there, as well as a peek at areas of the fabric where the pattern is either not yet obvious, or may not even be present.

Two thumbs up! Buy this book and sip or drink deeply of it: either method will be equally satisfying.


J. Kevin Colligan (jkcolligan2@home.com) is a past governor of the Maryland-DC-Virginia section of the MAA. He enjoys but does not have enough time for golf, running, go, and the piano. He loves New Orleans jazz, science fiction, and chili, and is always encouraging his New Orleans born and bred wife to cook more Creole dishes.

The table of contents is not available.