Gödel, Escher, Bach - ein Endloses Geflochtenes Band

einschränkender Sätze; könnte man nämlich immer wissen, welchen Weg man zu gehen hätte, könnte man einen Algorithmus konstruieren, mit dem sich jeder S ATZ beweisen ließe, und das würde den Satz von Church verletzen. Einen solchen Algorithmus gibt es nicht. (Ich überlasse es dem Leser, herauszufinden, wie das aus dem Satz von Church folgt.) Indessen bedeutet das nicht, daß es unmöglich wäre, überhaupt irgendwelche intuitive Vorstellungen zu haben, was ein vielversprechender Weg ist und was nicht. Tatsächlich haben die besten Programme eine sehr verfeinerte Heuristik, die ihnen erlaubt, Ableitungen in der Prädikatenlogik mit einer Geschwindigkeit vorzunehmen, die der von begabten Menschen vergleichbar ist.
    Der Trick bei der Beweisführung ist der, von der Tatsache Gebrauch zu machen, daß man ein Hauptziel hat — nämlich die Ketten, die man zu erzeugen wünscht —, das einen auch auf lokaler Stufe weiterführt. Eine Technik, die entwickelt wurde, um globale Ziele in lokale Strategien bei einer Ableitung zu verändern, nennt man Problemreduktion. Es beruht auf der Idee, daß wann immer man ein Fernziel hat, es üblicherweise Nahziele gibt, die, wenn man sie erreicht hat, behilflich sind, das Fern-

Abb. 115 . Zenos endloser „Zielbaum“, um von A nach B zu gelangen.
    ziel zu erreichen. Wenn man deshalb ein gegebenes Problem in eine Reihe neuer Teilprobleme aufbricht, diese dann in Teilteilprobleme aufbricht und so weiter auf rekursive Weise, kommt man schließlich zu ganz bescheidenen Zielen, die vermutlich in einigen wenigen Schritten zu erreichen sind. Oder es sieht zumindest so aus ...
    Problemreduktion brachte Zeno in Schwierigkeiten. Man erinnert sich, daß Zenos Methode von A nach B zu gelangen (man betrachte B als Ziel) die ist, das Problem auf zwei Teilprobleme zu „reduzieren“: zuerst die Hälfte des Weges gehen, dann den Rest des Weges. Nun hat man zwei Teilziele auf den „Zielstapel gepusht“ (im Sinn von Kapitel V). Jedes wird wiederum durch zwei Teilteilziele ersetzt — und so weiter ad infinitum. Schließlich hat man einen unendlichen Stapel von Zielen anstatt ein einziges Ziel (Abb. 115). Eine unendliche Anzahl von Zielen vom Stapel „wegzupoppen“ erweist sich als problematisch — und genau darauf kommt es Zeno natürlich an.
    Ein anderes Beispiel unendlicher Rekursion kam in dem Dialog Kleines harmonisches Labyrinth vor, als Achilles' Typ-freier Wunsch erfüllt werden sollte. Die Erfüllung mußte hinausgeschoben werden, bis die Erlaubnis vom Meta-Geist eintraf, aber um die Erlaubnis zu erhalten, die Erlaubnis zu erteilen, mußte er den Meta-Meta-Geist anrufen usw. Trotz der Unendlichkeit des Zielstapels bekam Achilles, was er gewünscht hatte. Problemreduktion hatte gesiegt.
    Ungeachtet meines Spottes ist Problemreduktion eine leistungsfähige Technik zur Verwandlung von Global- in Lokalprobleme. In gewissen Situationen glänzt sie, wie etwa beim Endspiel im Schach, wo die Vorausschautechnik oft jämmerlich versagt, selbst wenn man sie bis zur Lächerlichkeit ausdehnt, wie fünfzehn oder mehr Züge. Das rührt daher, daß die Vorausschautechnik nicht auf Plänen beruht; sie hat ganz einfach keine Ziele und untersucht eine riesige Menge sinnloser Alternativen. Wenn man ein Ziel hat, ist man in der Lage, eine Strategie zu dessen Erreichung zu entwerfen, und das ist eine völlig andere Philosophie als die der mechanischen Vorausschau. Bei der Vorausschautechnik wird natürlich die Wünschbarkeit oder ihr Fehlen durch die Bewertungsfunktion der Stellungen beurteilt, und das enthält indirekt eine Anzahl von Zielen, vor allem das, nicht mattgesetzt zu werden. Aber das ist zu indirekt. Gute Schachspieler, die gegen Vorausschau-Schachprogramme antreten, erhalten meistens den Eindruck, daß ihre Gegner in der Formulierung von Plänen oder Strategien sehr schwach sind.
Shandy und der Knochen
    Dafür, daß die Methode der Problemreduktion funktioniert, gibt es keine Garantie. In vielen Situationen versagt sie. Man betrachte etwa das folgende einfache Problem: Sie sind ein Hund, und ein befreundeter Mensch hat soeben ihren Lieblingsknochen über einen Drahtzaun in einen anderen Hof geworfen. Sie können den Knochen durch den Zaun hindurch sehen, wie er dort — und wie verführerisch! — im Grase liegt. Etwa fünfzehn Meter vom Knochen entfernt befindet sich ein offenes Tor im Zaun. Was soll man tun? Einige Hunde rennen einfach zum Zaun, stellen sich vor ihn hin und bellen, anderen