Computers Ltd.: What They Really Can't Do

D. Harel, Computers Ltd.: What They Really Can't Do, Oxford University Press, September 2000.

Revised paperback edition, 2003.   (German , 2002; Italian, 2002; Chinese, 2003; Hebrew, 2004.)

Table of Contents

  1. What's it all about?
    Algorithms
    Basic instructions
    The text vs. the process
    Inputs
    What do algorithms solve?
    Isn't our setup too simplistic?
    Solving algorithmic problems
    Programming
    Errors and correctness
    Termination
     
  2. Sometimes we can't do it
    Finite problems are solvable
    The tiling problems
    Do we really mean it?
    Elementary computing devices
    The Church/Turing thesis
    Computability is robust
    Unboundedness is misleading
    Program verification
    The halting problem
    Some problems are even worse!
     
  3. Sometimes we can't afford to do it
    Resources: time and memory space
    Improving running time
    Upper and lower bounds
    So what?
    The towers of Hanoi
    The good, the bad, and the ugly
    Intractability
    Roadblocks and chess
    Problems that are even harder
    Unreasonably large memory
     
  4. Sometimes we just don't know
    The monkey puzzle
    NP-complete problems
    Finding short paths
    Scheduling and matching
    More on puzzles
    Coloring networks
    Magic coins
    Standing or falling together
    The great mystery: Is P equal to NP?
    Can we come close?
    Sometimes we succeed
     
  5. Trying to ease the pain
    Parallelism, or joining forces
    Fixed vs. expanding parallelism
    Can parallelism eliminate the bad news?
    More unknowns in parallel computation
    Randomization, or tossing coins
    More on Monte Carlo algorithms
    Testing for primality
    Randomized primality testing
    Can randomization eliminate the bad news?
    Can computers simulate true randomness?
    Quantum computing
    Quantum algorithms
    Can there be a quantum computer?
    Molecular computing
     
  6. Turning bad into good
    Classical cryptography
    Public-key cryptography
    Signing messages
    Can all this be made to work?
    The RSA Cryptosystem
    Interactive proofs
    Zero-knowledge proofs
    I can 3-color a network
    On millionaires, ballots and more
     
  7. Are we ourselves any better?
    Algorithmic intelligence?
    The Turing test
    ELIZA and zupchoks
    Heuristics
    Representing knowledge
    Understanding natural language
    In conclusion 

.

Preface

In 1984, TIME magazine ran a cover story on computer software. In the otherwise excellent article, the editor of a certain software magazine was quoted as saying:

"Put the right kind of software into a computer, and it will do whatever you want it to. There may be limits on what you can do with the machines themselves, but there are no limits on what you can do with software."

Wrong. Totally wrong. In fact, a simple way of summarizing this book, is to say that it is devoted to describing and explaining the facts that refute --- no, shatter! --- this claim.

Of course, computers are incredible. They are without doubt the most important invention of the 20th century, having dramatically and irrevocably changed the way we live, and mostly for the better. But that is the good news, and good news is what most computer books are about. This book concentrates on the bad, on the negative side of things.

Computers are expensive, which is already bad news. They frustrate us: programming them is laborious and using them can be difficult; they are seductive, luring us away from more important things; they err; they crash; they contract viruses; and on and on. But it is not these kinds of bad news that concern us here. The goal of the book is to explain and illustrate one of the most important and fundamental facets of the world of computing --- its inherent limitations.

Typically, when people have difficulties bending computers to their will, their excuses fall into three categories: insufficient money, insufficient time, and insufficient brains. Being richer, the argument goes, could buy us larger and more sophisticated computers, supported by better software; being younger or having a longer life-span would enable us to wait longer for time-consuming programs to terminate; and being smarter could lead to solutions that we don't seem able to find. These are strong and valid points, and we are not about to contest them: a more generous supply of any of these three commodities could indeed take us a long way. However, for the most part, our book is not about these kinds of hardships either. It concentrates on bad news that is proven, lasting and robust, concerning problems that computers are not able to solve, regardless of our hardware, software, talents or patience. And when we say "proven", we mean really proven; that is, mathematically, and not just experimentally.

_________

Why are we interested in bad news? Shouldn't computer scientists be spending their time making things smaller, faster, easier, more accessible and more powerful? Well, they should, and the vast majority of us actually do. But even so, starting in the 1930s, and increasingly so by the year, many researchers have been working hard to better understand the other side of the coin, that of humbling the computer, by discovering and better understanding its inherent weaknesses.

The motivation for this quest is four-fold:

  • To satisfy intellectual curiosity. Just as physicists want to determine the ultimate confines of the universe or the constraints imposed by the laws of physics, so do computer scientists want to discover what can be computed and what cannot, and how costly it is when it can.
  • To discourage futile efforts. Many people, among them knowledgeable computer experts, try to tackle computational problems that happen to be subject to devastating bad news. The more we understand these problems and their inherent nature, the less we shall waste our time and energy.
  • To encourage development of new paradigms. Parallelism, randomization, heuristics, and quantum computing, four of the most promising and exciting topics in computer science research, would not be developing the way they are without the push resulting from the bad news.

  • To make possible the otherwise impossible. To make possible the impossible?! This is surely paradoxical. How on earth can we hope to profit from bad news? Well, to keep up suspense until Chapter 6, we shall only remark here that this is an unexpected aspect of our story, but also a surprisingly beneficial one.


    So much for motivation. As to the nature of the bad news we discuss, consider the large body of very exciting work aimed at endowing computers with human-like intelligence. In its wake, a host of questions arise concerning the limits of computation, such a whether computers can run companies, carry out medical diagnosis, compose music or fall in love. While promising, and often quite amazing, progress has been made in addressing these issues (not very much on the last one, however), these questions are posed in an imprecise and vague manner. With the exception of the last chapter of the book, we are not interested in them here. In contrast, we concentrate on precisely defined computational problems, that come complete with clear-cut objectives. This, in turn, makes it possible to make equally clear-cut statements about whether or not they can be solved satisfactorily.

The issues we discuss are not debatable, and do not involve philosophical, quasi-scientific arguments. Rather, we concentrate on hard facts, rigorously stated and mathematically proved. You don't go looking for triangles whose angles add up to 150 degrees or 200 degrees --- although no-one has ever been able to inspect each and every triangle --- simply because there is a proof that no such triangles exist*. In a similar way, if a computational problem has been proved to admit no solution, and we shall discuss such problems, then seeking a solution is pointless. The same goes for problems that do have solutions, but have been proved to require wholly unreasonably large computers (say, much larger than the entire known universe) or to take wholly unreasonable amounts of computation time (say, a lot more than the time since the Big Bang), and we shall discuss many of these too.

*Planar ones, of course. On a spherical or almost spherical surface, such as the planet Earth, the sum of the angles of a triangle is in fact greater than 180 degrees.

_____


By and large, people are unaware of the issues this book addresses. Sadly and surprisingly, this is true also for many members of the computing profession itself, as the quote from TIME shows. This is really unfortunate. If the bad news were some esoteric, recently discovered phenomenon, not having come across it could be understood. The truth is that some parts of our story have been known for almost 70 years, long before real computers were built, and most of the others have been steadily unfolding for the last 30.

To a large extent, the blame is on us, researchers in computer science. We have done far too little in exposing, exemplifying, illustrating, and making comprehensible the basics of our science in general, and its negative facets in particular. This leaves the public in general blissfully unstirred, free to follow with awe the technological advances in hardware and software, to delight in the excitement of new applications, and to gloat over the futuristic possibilities raised by instantaneous telecommunication, multimedia, virtual reality, artificial intelligence, and the internet revolution.

There is no reason to break up the party. We should continue to strive for bigger and better things. But even so, a measure of humility is in place: computers are not omnipotent --- far from it. Moreover, the problem is real, and it is here to stay.

.

Book Covers

Original edition, 2000 German translation, 2002 Hebrew translation, 2004
Paperback edition, 2003 Chinese translation, 2003 Italian translation, 2002
Polish translation, 2002 Special printing, 2012 New Hebrew version, 2012