Aus der Amazon.de-Redaktion
Überraschend und provokant: Da geht tatsächlich jemand hin und behauptet, dass Computer "beschränkt" sind und widmet 200 Seiten der Tatsache, dass es Probleme gibt, die "zu lösen Computer einfach nicht in der Lage sind". Im Moment nicht und wahrscheinlich nie, so jedenfalls sei es mathematisch eindeutig bewiesen und auch alles andere als eine neue Erkenntnis, behauptet David Harel, israelischer Wissenschaftler mit den Schwerpunkten Logik der Programmierung und Berechenbarkeit. Klingt trocken, ist aber hochgradig spannend und im Buch mit vielen praktischen Beispielen anschaulich und plakativ umgesetzt.
Nie bewältigen wird ein Computer beispielsweise das Affenpuzzle, quadratische Karten mit einem halben Affen, jeweils obere und untere Hälfte, an jeder Seite, dazu farbig unterschiedlich. Der Rechner bräuchte "über 533 Quadrillionen Jahre, um ein einzelnes Beispiel mit 25 Karten zu lösen". Verrückt? Keineswegs, im Gegenteil, nur eines von vielen Problemen, die einen Rechner, mag er groß sein, wie er will, regelrecht alt aussehen lassen: Stundenplanprobleme oder die Fragestellung, wie man für verschiedene Variablen die kürzeste Verbindung findet, sie gehören dazu. Weiterhelfen könnten da Quanten- oder Molekularcomputer, an denen Forscher fieberhaft arbeiten.
Das Buch für Laien mit mathematischen Grundkenntnissen, es hat es in sich, aber man sollte schon etwas mehr als mathematisch interessiert sein, um das Buch dann aber auch als wirkliche Herausforderung anzusehen. Vielleicht regt es sogar zum Philosophieren an: "Jemand sagte einmal, die Frage, ob Computer denken können, gleiche der Frage, ob U-Boote schwimmen können." --Barbara Wegmann
Spektrum der Wissenschaft
Der Physik ist es in vorbildlicher Weise gelungen, ihre Erkenntnisse in die breitere Öffentlichkeit zu transportieren. Sie hatte es leicht bei explosiven Themen wie der Atomtheorie, aber selbst so Schwieriges wie Quantenphysik oder Schwarze Löcher findet sich in populärwissenschaftlichen Werken gut verständlich erklärt. Zur Informatik dagegen gibt es außer der Fachliteratur vor allem Bücher, die uns eine schöne neue Welt versprechen. Das ist nur ein Teil der Wahrheit. Wie in jeder Wissenschaft stehen Errungenschaften, die uns das Leben erleichtern, solchen von eher zweifelhaftem Wert gegenüber. Und es gibt Grenzen des Machbaren und des mit den vorhandenen Ressourcen Machbaren.
Diese Grenzen sind das Thema des Buches von David Harel vom weltberühmten Weizmann-Institut in Rehovot (Israel). Der englische Titel "Computers Ltd.: what they really can’t do" gibt sein Anliegen viel deutlicher wieder als der deutsche (insgesamt ist die Übersetzung aber gut gelungen). Was also können Rechner nicht nur "noch nicht", sondern prinzipiell nicht? Können wir derartig weit reichende Resultate auch im mathematischen Sinn beweisen? Wir können - und das ergibt ein faszinierendes Forschungsgebiet, die Komplexitätstheorie und die Berechenbarkeitstheorie.
Natürlich müssen die Fragen präzisiert werden. Könnte ein Rechner eingesetzt werden, um aus einer Gerichtsverhandlung ein Urteil zu berechnen? Schon, aber die Auswirkungen wären vermutlich schlimm. Darum geht es in diesem Buch nicht. Rechner können bisher nur schlecht Texte in eine andere Sprache übersetzen. Auch darum geht es nicht, weil wir nur schwer richtige von falschen Ergebnissen abgrenzen können.
Was bleibt dann? Sehr viel: alle Optimierungsprobleme aus den Natur- und Ingenieurwissenschaften und dem Alltag mit einem gut überprüfbaren Optimierungsziel, aber auch Fragen über die Lösbarkeit von Problemen oder die Korrektheit von Lösungsverfahren. Zudem sind wir an allgemeinen Problemen interessiert. Also nicht am kürzesten Weg von Dortmund nach Moskau, auch nicht an der kürzesten Verbindung zwischen zwei beliebigen Städten auf unserem Erdball, sondern an einem Verfahren, das zu einer Liste von beliebig, aber endlich vielen Orten und Verbindungen (mit Längenangaben) zwischen einigen Orten kürzeste Wege findet. Dies ist keine Einschränkung, da Rechnerlösungen von dieser allgemeinen Art sind.
Rechner können nicht alle von uns zugelassenen Probleme lösen, weil es viel mehr (allgemeine) Probleme als Lösungsverfahren gibt. Dies kann man beweisen, aber so geht das Buch nicht vor. Harel betrachtet stets konkrete Probleme. Er diskutiert keine mathematischen Beweise, sodass das Buch gut verständlich bleibt; stattdessen begründet er seine Behauptungen eindringlich, überzeugend und mit einer bildhaften Sprache.
Eine solche Behauptung ist: Es gibt keinen Algorithmus, der für ein beliebiges Computerprogramm, das auf Listen von Zahlen operiert, entscheidet, ob es jede Zahlenliste aufsteigend sortiert. Wohlgemerkt: Für viele Programme können wir dies nachweisen, aber nicht allgemein.
Andere Probleme sind prinzipiell lösbar, aber so schwer, dass die Ressourcen unseres Universums nicht ausreichen, sie zu lösen.
Noch faszinierender ist die Frage, die unter dem Namen "P=NP?" berühmt geworden ist. Tausende von Problemen, darunter viele der täglich zu lösenden Optimierungsprobleme, gehören zu der Problemklasse NP. Wir wissen nicht, ob sie effizient (mit realistischen Ressourcen) lösbar sind oder nicht. Wir wissen aber, dass sie alle effizient lösbar sind oder alle nicht effizient lösbar sind. Das Buch stellt anschaulich dar, wie derartige Ergebnisse erzielt werden. Die Fachwelt ist sich einig, dass auch hier die schlechte Nachricht "nicht effizient lösbar" wahr ist.
Aber sind schlechte Botschaften nur schlecht? Kryptografie, die Verschlüsselung von Daten, beruht ja gerade darauf, dass legale Nutzer einen Vorteil gegenüber illegalen haben. Moderne Kryptosysteme sind prinzipiell knackbar - nur hat niemand die dafür nötigen Ressourcen.
Das Buch ist von einem weltbekannten Experten in einem unvergleichbaren Stil geschrieben: leicht und locker und dennoch präzise. Notwendige Vereinfachungen führen nicht zu nur noch fast richtigen Aussagen. Wer abstrakte Gedanken nicht fürchtet, wird dieses Buch mit Genuss lesen und hinterher die Informatik mit anderen Augen sehen.
Eine kleine Ergänzung: David Harel wählt häufig den Test, ob eine Zahl Primzahl ist, als Beispiel. Im vergangenen Jahr haben Manindra Agrawal, Neeraj Kayal und Nitin Saxena aus Kanpur gezeigt, dass dieses Problem effizient lösbar ist - es gibt also auch gute Nachrichten.
Diese Grenzen sind das Thema des Buches von David Harel vom weltberühmten Weizmann-Institut in Rehovot (Israel). Der englische Titel "Computers Ltd.: what they really can’t do" gibt sein Anliegen viel deutlicher wieder als der deutsche (insgesamt ist die Übersetzung aber gut gelungen). Was also können Rechner nicht nur "noch nicht", sondern prinzipiell nicht? Können wir derartig weit reichende Resultate auch im mathematischen Sinn beweisen? Wir können - und das ergibt ein faszinierendes Forschungsgebiet, die Komplexitätstheorie und die Berechenbarkeitstheorie.
Natürlich müssen die Fragen präzisiert werden. Könnte ein Rechner eingesetzt werden, um aus einer Gerichtsverhandlung ein Urteil zu berechnen? Schon, aber die Auswirkungen wären vermutlich schlimm. Darum geht es in diesem Buch nicht. Rechner können bisher nur schlecht Texte in eine andere Sprache übersetzen. Auch darum geht es nicht, weil wir nur schwer richtige von falschen Ergebnissen abgrenzen können.
Was bleibt dann? Sehr viel: alle Optimierungsprobleme aus den Natur- und Ingenieurwissenschaften und dem Alltag mit einem gut überprüfbaren Optimierungsziel, aber auch Fragen über die Lösbarkeit von Problemen oder die Korrektheit von Lösungsverfahren. Zudem sind wir an allgemeinen Problemen interessiert. Also nicht am kürzesten Weg von Dortmund nach Moskau, auch nicht an der kürzesten Verbindung zwischen zwei beliebigen Städten auf unserem Erdball, sondern an einem Verfahren, das zu einer Liste von beliebig, aber endlich vielen Orten und Verbindungen (mit Längenangaben) zwischen einigen Orten kürzeste Wege findet. Dies ist keine Einschränkung, da Rechnerlösungen von dieser allgemeinen Art sind.
Rechner können nicht alle von uns zugelassenen Probleme lösen, weil es viel mehr (allgemeine) Probleme als Lösungsverfahren gibt. Dies kann man beweisen, aber so geht das Buch nicht vor. Harel betrachtet stets konkrete Probleme. Er diskutiert keine mathematischen Beweise, sodass das Buch gut verständlich bleibt; stattdessen begründet er seine Behauptungen eindringlich, überzeugend und mit einer bildhaften Sprache.
Eine solche Behauptung ist: Es gibt keinen Algorithmus, der für ein beliebiges Computerprogramm, das auf Listen von Zahlen operiert, entscheidet, ob es jede Zahlenliste aufsteigend sortiert. Wohlgemerkt: Für viele Programme können wir dies nachweisen, aber nicht allgemein.
Andere Probleme sind prinzipiell lösbar, aber so schwer, dass die Ressourcen unseres Universums nicht ausreichen, sie zu lösen.
Noch faszinierender ist die Frage, die unter dem Namen "P=NP?" berühmt geworden ist. Tausende von Problemen, darunter viele der täglich zu lösenden Optimierungsprobleme, gehören zu der Problemklasse NP. Wir wissen nicht, ob sie effizient (mit realistischen Ressourcen) lösbar sind oder nicht. Wir wissen aber, dass sie alle effizient lösbar sind oder alle nicht effizient lösbar sind. Das Buch stellt anschaulich dar, wie derartige Ergebnisse erzielt werden. Die Fachwelt ist sich einig, dass auch hier die schlechte Nachricht "nicht effizient lösbar" wahr ist.
Aber sind schlechte Botschaften nur schlecht? Kryptografie, die Verschlüsselung von Daten, beruht ja gerade darauf, dass legale Nutzer einen Vorteil gegenüber illegalen haben. Moderne Kryptosysteme sind prinzipiell knackbar - nur hat niemand die dafür nötigen Ressourcen.
Das Buch ist von einem weltbekannten Experten in einem unvergleichbaren Stil geschrieben: leicht und locker und dennoch präzise. Notwendige Vereinfachungen führen nicht zu nur noch fast richtigen Aussagen. Wer abstrakte Gedanken nicht fürchtet, wird dieses Buch mit Genuss lesen und hinterher die Informatik mit anderen Augen sehen.
Eine kleine Ergänzung: David Harel wählt häufig den Test, ob eine Zahl Primzahl ist, als Beispiel. Im vergangenen Jahr haben Manindra Agrawal, Neeraj Kayal und Nitin Saxena aus Kanpur gezeigt, dass dieses Problem effizient lösbar ist - es gibt also auch gute Nachrichten.
Rezensent: Ingo Wegener
Pressestimmen
"... David Harel vermittelt die mathematischen Fakten spannend, unterhaltsam und allgemeinverständlich. ... Eine tour de force mit überraschenden Aspekten, die den Leser - ob vorgebildeter Laie oder Fachkundiger - fesseln wird." Stormarner Tageblatt 24.4.04 "... Das Buch ist von einem weltbekannten Experten in einem unvergleichbaren Stil geschrieben: leicht und locker und dennoch präzise. Notwendige Vereinfachungen führen nicht nur zu nur noch fast richtigen Aussagen. Wer abstrakte Gedanken nicht fürchtet, wird dieses Buch mit Genuss lesen und hinterher die Informatik mit anderen Augen sehen. ...." Ingo Wegener, Spektrum der Wissenschaft November 2003 "...Zweifellos umfasst dieses Buch einen in der Praxis enorm wichtigen Bereich der Computer-Wissenschaft. Auf diesem Gebiet kennen sich selbst Computerfachleute wenig aus, und der Öffentlichkeit ist es weitgehend unbekannt. Harel hat ein verständliches und gleichzeitig wissenschaftlich fundiertes Buch geschrieben. Die Referenzen zu den Originalbeiträgen sind für den Spezialisten interessant, können aber vom breiten Leserpublikum problemlos beiseite gelassen werden. Ein Buch also, das als Referenz in einer wissenschaftlichen Veröffentlichung durchaus nicht fehl am Platze ist. Gleichzeitig spricht es jedoch einen großen Leserkreis an und ist für Computer-Wissenschaftler ganz praktisch von Nutzen. Es eignet sich sogar für Einführungsvorlesungen, auch wenn in den meisten Computerwissenschaft-Kursen eine ausgeprägtere Behandlung mathematischer Themen erwartet wird. Ein knapper Index macht das Buch zu einem nützlichen Nachschlagewerk. Harels Stil ist einfach und gleichwohl überzeugend in seiner wissenschaftlichen Kompetenz. Damit ist das Buch einzigartig. Es gehört mit gleicher Berechtigung in die Bücherregale von Computerwissenschaftlern praktisch jeder Disziplin, in öffentliche Bibliotheken und in alle Buchhandlungen." London Times, Higher Education Supplement, July 2001
Kurzbeschreibung
In einer brillanten tour de force beweist der bekannte Computer-Wissenschaftler David Harel bestechend logisch, dass selbst die leistungsstärksten Computer der Welt nicht alles können und niemals können werden. Eine provokative, mit Überraschungen gewürzte Botschaft, die uns an die Grenzen allen Wissens führt.
Über den Autor
David Harel ist der Dekan der Fakultät für Mathematik und Informatik des Weizmann-Instituts in Rehovot in Israel. Seine Forschungsinteressen liegen in der theoretischen Informatik, mit den Schwerpunkten Berechenbarkeit, Automatentheorie und Logik der Programmierung. Im Jahr 1992 erhielt er für herausragende Lehre den Karlstrom-Preis der Association for Computing Machinery und 1997 den Softwarepreis des israelischen Ministerpräsidenten. David Harel ist vielfacher Buchautor, und wurde einer breiteren Öffentlichkeit durch eine Reihe von Fernsehinterviews bekannt, die er mit herausragenden Mthematikern und Informatikern für einen israelischen Sender durchführte.
