Computers Ltd.: What They Really Can't Do

by David Harel

Hardcover, 2003

Status

Available

Call number

004

Library's review

Indeholder "Preamble", "Acknowledgments", "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", "
Show More
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. Can we ourselves do any better?", " Algorithmic intelligence?", " The Turing test", " ELIZA and zupchoks", " Heuristics", " What is knowledge?", " Understanding natural language", "Postramble", "Index".

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

Publication

Oxford University Press, USA (2003), Paperback, 240 pages

Description

Computers are incredible. They are one of the most important inventions of the 20th century, dramatically and irrevocably changing the way we live. That is the good news. The bad news is that there are still major limitations to computers, serious problems that not even the most powerfulcomputers can solve. The consequences of such limitations can be serious. Too often these limits get overlooked, in the quest for bigger, better, and more powerful computers. In Computers Ltd., David Harel, best-selling author of Algorithmics, explains and illustrates one of the most fundamental,yet under-exposed facets of computers - their inherent limitations. Looking at the bad news that is proven, lasting and robust, discussing limitations that no amounts of hardware, software, talents or resources can overcome, the book presents a disturbing and provocative view of computing at thestart of the 21st century. Along the way he shows just how far from perfect computers are, while shattering some of the many claims made for these machines. Though we may strive for bigger and better things in computing, we need to be realistic: computers are not omnipotent - far from it. Moreover,the problem is real and here to stay.… (more)

User reviews

LibraryThing member fpagan
A nice little popularization of the basic results of computability theory and computational complexity theory. Readable in polynomial time.

Language

Original language

English

Physical description

240 p.; 17.9 cm

ISBN

0198505558 / 9780198505556

Local notes

Omslag: Tony Stone
Omslaget viser en finger, der udløser gnister ved at røre ved et tastatur
Omslagsbillede: Tony Stone Images
Indskannet omslag - N650U - 150 dpi
Computers Limited.: What They Really Cant Do

Pages

240

Library's rating

Rating

(6 ratings; 3.3)

DDC/MDS

004
Page: 0.1706 seconds