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.
Author(s): David Harel
Year: 2000
Language: English
Pages: 238
Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0013.djvu
Preamble......Page __sk_0005.djvu
Acknowledgments......Page __sk_0011.djvu
1 What's it all about?......Page __sk_0017.djvu
Algorithms......Page __sk_0018.djvu
Basic instructions......Page __sk_0021.djvu
The text vs. the process......Page __sk_0023.djvu
Inputs......Page __sk_0025.djvu
What do algorithms solve?......Page __sk_0026.djvu
Isn't our setup too simplistic?......Page __sk_0031.djvu
Solving algorithmic problems......Page __sk_0032.djvu
Programming......Page __sk_0034.djvu
Errors and correctness......Page __sk_0037.djvu
Termination......Page __sk_0042.djvu
2 Sometimes we can't do it......Page __sk_0043.djvu
Finite problems are solvable......Page __sk_0045.djvu
The tiling problem......Page __sk_0046.djvu
Do we really mean it?......Page __sk_0049.djvu
Elementary computing devices......Page __sk_0052.djvu
The Church-Turing thesis......Page __sk_0056.djvu
Computability is robust......Page __sk_0058.djvu
Domino snakes......Page __sk_0062.djvu
Program verification......Page __sk_0064.djvu
The halting problem......Page __sk_0066.djvu
Nothing about computation can be computed!......Page __sk_0069.djvu
Some problems are even worse......Page __sk_0070.djvu
3 Sometimes we can't afford to do it......Page __sk_0075.djvu
Resources: time and memory space......Page __sk_0076.djvu
Improving running time......Page __sk_0077.djvu
Upper and lower bounds......Page __sk_0081.djvu
The towers of Hanoi......Page __sk_0085.djvu
The good, the bad, and the ugly......Page __sk_0089.djvu
Intractability......Page __sk_0094.djvu
Roadblocks and chess......Page __sk_0098.djvu
Problems that are even harder......Page __sk_0101.djvu
Unreasonable memory requirements......Page __sk_0104.djvu
4 Sometimes we just don't know......Page __sk_0107.djvu
The monkey puzzle......Page __sk_0108.djvu
NP-complete problems......Page __sk_0111.djvu
Finding short paths......Page __sk_0113.djvu
Scheduling and matching......Page __sk_0116.djvu
More on puzzles......Page __sk_0118.djvu
Coloring networks......Page __sk_0120.djvu
Magic coins......Page __sk_0122.djvu
Standing or falling together......Page __sk_0125.djvu
The great mystery: is P equal to NP?......Page __sk_0127.djvu
Can we come close?......Page __sk_0129.djvu
Sometimes we succeed......Page __sk_0131.djvu
5 Trying to ease the paln......Page __sk_0135.djvu
Parallelism, or joining forces......Page __sk_0137.djvu
Can parallelism eliminate the bad news?......Page __sk_0140.djvu
Randomization, or tossing coins......Page __sk_0145.djvu
More on Monte Carlo algorithms......Page __sk_0148.djvu
Testing for primality......Page __sk_0150.djvu
Randomized primality testing......Page __sk_0152.djvu
Can randomization eliminate the bad news?......Page __sk_0156.djvu
Can computers simulate true randomness?......Page __sk_0157.djvu
Quantum computing......Page __sk_0159.djvu
Quantum algorithms......Page __sk_0162.djvu
Can there be a quantum computer?......Page __sk_0167.djvu
Molecular computing......Page __sk_0169.djvu
6 Turning bad into good......Page __sk_0173.djvu
Classical cryptography......Page __sk_0174.djvu
Public-key cryptography......Page __sk_0177.djvu
Signing messages......Page __sk_0181.djvu
Can this be made to work?......Page __sk_0184.djvu
The RSA cryptosystem......Page __sk_0186.djvu
Interactive proofs......Page __sk_0189.djvu
Zero-knowledge proofs......Page __sk_0193.djvu
I can 3-color a network......Page __sk_0196.djvu
On millionaires, ballots, and more......Page __sk_0202.djvu
7 Can we ourselves do any better?......Page __sk_0205.djvu
Algorithmic intelligence?......Page __sk_0207.djvu
The Turing test......Page __sk_0208.djvu
ELIZA and zupchoks......Page __sk_0212.djvu
Heuristics......Page __sk_0215.djvu
What is knowledge?......Page __sk_0220.djvu
Understanding natural language......Page __sk_0224.djvu
Postramble......Page __sk_0229.djvu
Index......Page __sk_0231.djvu
