Das Affenpuzzle: und weitere bad news aus der Computerwelt [Gebundene Ausgabe]

Ü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

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.

Rezensent: Ingo Wegener