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

ist? Den Ausgangspunkt unserer Beweisführung wird der Versuch bilden, das Diagonalverfahren auf FlooP anzuwenden — genau wie wir es für BlooP taten. Wir werden sehen, daß zwischen den beiden Fällen subtile, aber wichtige Unterschiede bestehen.
    Wie im Fall von BlooP wollen wir uns den Vorrat aller FlooP-Programme vorstellen. Wir werden ihn den „Pool F“ nennen. Dann führen wir dieselben Filteroperationen durch, so daß wir schließlich erhalten:
    Einen vollständigen Vorrat aller aufruflosen FlooP-Programme, die Funktionen mit genau einem Input-Parameter berechnen.
    Nennen wir diese speziellen FlooP-Programme Grüne Programme (da sie immer weiterfahren können).
    Wie wir nun alle Blauen Programme mit einer Indexzahl versahen, so können wir es auch mit den Grünen Programmen tun, indem wir sie in einem Katalog anordnen, bei dem jeder Band alle Grünen Programme einer festen Länge in alphabetischer Reihenfolge enthält.
    Bis zu diesem Punkt bringt der Übergang von BlooP zu FlooP keine Komplikationen mit sich. Nun wollen wir aber sehen, ob sich auch der letzte Teil übertragen läßt, nämlich der Diagonaltrick. Was geschieht beim Versuch, eine Diagonalfunktion zu definieren?
    Gründiag [ N ] = 1 + Grünprogramm {Nr. N } [ N ]
    Plötzlich taucht ein Hindernis auf: diese Funktion Gründiag [ N ] hat vielleicht nicht für alle Input-Werte N einen wohldefinierten Output-Wert. Das rührt einfach daher, daß wir die nicht-endenden Programme im F-Vorrat nicht ausgesiebt haben, und deshalb haben wir keine Garantie, daß wir Gründiag [ N ] für alle Werte von N berechnen können. Manchmal können wir uns auf Berechnungen einlassen, die nie ein Ende finden. Und in solchen Fällen läßt sich die Diagonalmethode nicht anwenden, denn das hängt davon ab, ob die Diagonalfunktion für alle möglichen Inputs einen Wert besitzt.
Der Endend?-Tester gibt uns Rote Programme
    Um dem abzuhelfen, müßten wir uns eines Endend?-Testers bedienen, wenn es einen gäbe. Führen wir also mit Bedacht die auf wackligen Füßen stehende Annahme ein, daß es einen gibt, und verwenden wir ihn als unseren vierten Filter. Wir folgen der Liste der Grünen Programme und merzen, einen nach dem anderen, alle Nicht-Endenden aus, so daß uns schließlich übrigbleibt:
    Ein vollständiger Vorrat aller aufruflosen FlooP-Programme, die Funktionen mit genau einem Input-Parameter berechnen und die bei allen Input-Werten ein Ende finden.
    Nennen wir diese speziellen FlooP-Programme Rote Programme (da sie alle stoppen müssen). Jetzt läßt sich das Diagonal-Argument anwenden. Wir definieren:
    Rotdiag [ N ] = 1 + Rotprogramm {Nr. N } [ N ]
    und genau wie bei Blaudiag kommen wir zu dem Schluß, daß Rotdiag [ N ] eine wohldefinierte, berechenbare Funktion einer Variablen ist, die nicht im Katalog der Roten Programme steht und sich sogar in der leistungsfähigen Sprache FlooP nicht berechnen läßt. Vielleicht ist es an der Zeit, zu GlooP überzugehen?
GlooP ...
    Ja — aber was ist GlooP? Wenn FlooP ein entfesseltes BlooP ist, dann muß GlooP ein entfesseltes FlooP sein. Wie kann man aber die Fesseln zweimal ablegen? Wie eine Sprache herstellen, deren Kraft die von FlooP übersteigt? Mit Rotdiag haben wir eine Funktion gefunden, deren Wert wir Menschen berechnen können — die Methode, wie das zu geschehen hat, wurde explizit in deutscher Sprache beschrieben —, die aberanscheinend in der Sprache FlooP nicht programmiert werden kann. Dies ist ein ernstzunehmendes Dilemma, weil noch nie jemand eine leistungsfähigere Computersprache als FlooP entdeckt hat.
    Man hat sorgfältige Untersuchungen über die Leistungsfähigkeit von Computersprachen durchgeführt. Wir brauchen das nicht selbst zu tun, wir notieren lediglich, daß es eine riesige Klasse von Computersprachen gibt, von denen sich beweisen läßt, daß sie genau die gleiche Aussagekraft haben wie FlooP, und zwar in diesem Sinn: Jede Berechnung, die in irgendeiner dieser Sprachen programmiert werden kann, kann in allen programmiert werden. Das kuriose dabei ist, daß fast jeder vernünftige Versuch, eine Computersprache zu entwerfen, damit endet, daß man ein Mitglied dieser Klasse erzeugt, was bedeutet: eine Sprache von gleicher Leistungsfähigkeit wie FlooP. Es braucht einige Mühe, eine einigermaßen interessante Computersprache zu erfinden, die schwächer ist als die dieser Klasse. Ein Beispiel einer schwächeren Sprache ist natürlich BlooP, aber es ist eher die Ausnahme als die Regel.