Können Computer alles? Wenn es so wäre, gäbe es dieses Buch nicht. Es beweist bestechend logisch, dass selbst die größten, schnellsten, intelligentesten und teuersten Computer der Welt nur beschränkt leistungsfähig sind. Der Mensch kann noch so viel Geld, Zeit und Know-how investieren, es gibt Computer-Probleme, die er niemals lösen wird. Eine beunruhigende, provokative Botschaft - und doch: wussten wir es nicht eigentlich schon, haben es aber nie wirklich glauben wollen? Der bekannte Computer-Wissenschaftler David Harel vermittelt die mathematischen Fakten spannend, unterhaltsam und allgemeinverständlich. Mit der Beschränktheit des Computers werden wir an die Grenzen allen Wissens geführt. Grenzen, die den Menschen beflügeln, das Mögliche weiter zu verbessern und selbst aus dem Unmöglichen Nutzen zu ziehen. Eine brillante tour de force mit überraschenden Aspekten, die den Leser - ob vorgebildeter Laie oder Fachkundiger - von der ersten bis zur letzten Seite fesselt.

Autorentext

David Harel is the Dean of the Faculty of Mathematics and Computer Science at the Weizmann Institute of Science in Israel. He is also co-founder of I-Logix, Inc., Andover, MA, and of SenseIT Technologies, Ltd. (DigiScents Israel). His research interests are in theoretical computer science (especially computability, automata theory and logics of programs), and in software and systems engineering (especially specification and modeling, object-oriented analysis and design, and visual languages), as well as the aesthetic layout of diagrams, clustering algorithms and the synthesis and communication of smell. He is the inventor of the language of statecharts (1983), was part of the team that designed the Statemate (1984-1987) and Rhapsody (1997) tools, and was co-inventor of LSCs (1998). His work is central to the behavioral aspects of the UML. He devotes part of his time to expository work: In 1984 he delivered a lecture series on Israeli radio, and in 1998 he hosted a series on Israeli television; some of his writing is intended for a general audience (see, for example, Computers Ltd.: What They Really Can't Do , Oxford University Press, September 2000). He has received a number of awards, including ACM's Karlstrom Outstanding Educator Award in 1992, and the 1997 Israeli Prime Minister's Award for Software. His book, Algorithmics: The Spirit of Computing (Addison-Wesley, 1987, 2nd. edn. 1992) was the Spring 1988 Main Selection of the Macmillan Library of Science. He is a Fellow of the ACM and of the IEEE.

Inhalt
1 Worum geht es überhaupt?.- Algorithmen.- Elementare Anweisungen.- Text und Prozeß.- Eingaben.- Was können Algorithmen?.- Vereinfachen wir nicht zu sehr?.- Algorithmische Probleme lösen.- Programmieren.- Fehler und Korrektheit.- Aufhören.- 2 Manchmal können wir es nicht.- Endliche Probleme sind lösbar.- Das Dominoproblem.- Meinen wir das wirklich?.- Elementare Berechnungsmodelle.- Die Church-Turing-These.- Berechenbarkeit ist robust.- Dominoschlangen.- Programmverifikation.- Das Halteproblem.- Berechenbarkeit ist unberechenbar!.- Manches ist noch unberechenbarer.- 3 Manchmal ist es zu teuer.- Ressourcen: Laufzeit und Speicherplatz.- Wie man die Laufzeit verbessern kann.- Obere und untere Schranken.- Na und?.- Die Türme von Hanoi.- Die guten, die schlechten und die häßlichen.- Undurchführbarkeit.- Roadblock und Schach.- Noch schwierigere Probleme.- Zu wenig Speicherplatz.- 4 Manchmal wissen wir es nicht.- Das Affenpuzzle.- NP-vollständige Probleme.- Kürzeste Wege finden.- Planen und Packen.- Mehr über Spiele.- Netze färben.- Magische Münzen.- Zusammen rauf, zusammen runter.- Das große Geheimnis: Gilt P = NP?.- Können wir uns annähern?.- Manchmal klappt's.- 5 Schmerzlindernde Mittel.- Parallelität oder zusammen sind wir stark.- Parallelität: wird alles gut?.- Randomisierung oder Münzen werfen.- Mehr über Monte-Carlo-Algorithmen.- Primzahltests.- Randomisierte Primzahltests.- Randomisierung: wird nun alles gut?.- Können Computer den Zufall simulieren?.- Quantencomputer.- Quantenalgorithmen.- Kann es Quantencomputer geben?.- Molekularcomputer.- 6 Schlechtes in Gutes verwandeln.- Klassische Kryptographie.- Public-Key-Kryptographie.- Unterschreiben.- Kann dies funktionieren?.- Das RSA-Kryptosystem.- Interaktive Beweise.- Zero-Knowledge-Beweise.- Ichkann ein Netz 3-färben!.- Über Millionäre, Wahlen und anderes.- 7 Können wir selbst es besser?.- Algorithmische Intelligenz?.- Der Turing-Test.- ELIZA und Zupchoks.- Heuristiken.- Was ist Wissen?.- Natürliche Sprache verstehen.- Nachgedanken.