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

eigenen Falle fängt.
    Die Wiederholbarkeit von Cantors Methode ähnelt der der diabolischen Schildkröten-Methode, um Herrn Krebs' Grammophone eines nach dem anderen zu zerschmettern, während sie mehr und mehr „hi-fi“ und — so hoffte zumindest Herr Krebs „vollkommen“ wurden. Diese Methode verlangt, daß man für jedes Grammophon eine besondere Melodie konstruiert, die das Grammophon nicht wiedergeben kann. Es ist kein Zufall, daß Cantors Trick und der von Herrn Schildkröte diese merkwürdige Wiederholbarkeit gemeinsam haben; man hätte den Contrakrostipunktus sehr wohl auch „Cantorkrostipunktus“ nennen können. Außerdem sind, wie Herr Schildkröte dem unschuldigen Achilles andeutet, die Geschehnisse im Contrakrostipunktus eine Paraphrase der Konstruktion, die Gödel beim Beweis seines Unvollständigkeitssatzes verwendet; daraus folgt, daß die Gödel-Konstruktion ebenfalls einer Diagonalkonstruktion sehr ähnlich ist. Das wird in den beiden folgenden Kapiteln klar werden.
Von BlooP zu FIooP
    Wir haben nunmehr die Klasse der primitiv-rekursiven Funktionen und der primitiv-rekursiven Eigenschaften natürlicher Zahlen mit Hilfe von Programmen in der BlooPSprache definiert. Auch haben wir gezeigt, daß BlooP nicht alle Funktionen der natürlichen Zahlen, die wir in Worten definieren können, einfängt. Wir konstruierten vermittels Cantors Diagonalmethode sogar eine „unBlooPbare“ Funktion: Blaudiag [ N ]. Was hat BlooP, daß es Blaudiag nicht repräsentieren kann? Wie könnte man BlooP verbessern, so daß Blaudiag repräsentierbar wird?
    Die Eigenschaft, die BlooP definierte, war die Begrenztheit seiner Schleifen. Und wenn wir nun diese Bedingung für Schleifen fallen lassen und eine zweite Sprachenamens „FlooP“ („F“ für „frei“) ersinnen? FlooP wird mit BlooP identisch sein — mit einer Ausnahme: Wir können sowohl Schleifen ohne Obergrenze wie solche mit einer Grenze haben (wenn auch der einzige Grund, warum man eine solche Obergrenze bei der Niederschrift einer Schleifen-Aussage In FlooP erwähnte, die Eleganz wäre). Diese neuen Schleifen werden wir MU-SCHLEIFEN nennen. Damit folgen wir der Konvention der mathematischen Logik, in der „freie“ Suchaktionen (d. h. solche ohne Grenzen) im allgemeinen durch ein Symbol angezeigt werden, das man „µ-Operator“ (mu-Operator) nennt. Schleifen-Aussagen in FlooP können also folgendermaßen aussehen:
MU-SCHLEIFE :
BLOCK n : ANFANG
.
.
.
BLOCK n : ENDE.
    Diese Eigenschaft wird uns gestatten, Tests in FlooP für Eigenschaften wie Wundersamkeit oder Schildkröten-Eigenschaft niederzuschreiben — Tests, die wir in BlooP wegen der potentiellen Offenheit bei der nötigen Suchaktion nicht zu programmieren wußten. Ich überlasse es dem interessierten Leser, einen FlooP-Test für Wundersamkeit abzufassen, der das Folgende leistet:
1)
Wenn sein Input, N , wundersam ist, dann stoppt das Programm und gibt die Antwort JA .
2)
Wenn N nicht wundersam ist, aber einen geschlossenen Zyklus erzeugt, der nicht 1 4-2-1-4-2-1-... ist, stoppt das Programm und gibt die Antwort NEIN .
3)
Wenn N nicht wundersam ist und eine „endlos reduplizierte Progression“ erzeugt, stoppt das Programm nie. Das ist FlooPs Art zu antworten, ohne zu antworten. FlooPs Nicht-Antwort hat eine merkwürdige Ähnlichkeit mit Jōshūs Nicht-Antwort „MU“.
    Die Ironie von Fall 3 ist die, daß OUTPUT immer den Wert NEIN hat, aber immer unerreichbar bleibt, da das Programm ja immer weiterläuft. Diese lästige dritte Möglichkeit ist der Preis, den wir für das Recht zahlen müssen, freie Schleifen niederzuschreiben. In allen FlooP-Programmen, die die MU-SCHLEIFEN Option enthalten, wird eine theoretische Alternative immer die der Nicht-Beendbarkeit sein. Natürlich gibt es viele FlooP-Programme, die tatsächlich für alle möglichen Input-Werte ein Ende finden. Wie ich bereits erwähnt habe, vermuten z. B. die meisten, die Wundersamkeit erforscht haben, daß ein FlooP-Programm wie das oben vorgeschlagene immer ein Ende finden wird, und überdies in jedem Fall mit der Antwort JA .
FlooP-Programme mit und ohne Ende
    Es wäre wohl äußerst wünschenswert, die FlooP-Prozeduren in zwei Klassen einzuteilen: endende und nicht-endende. Eine endende Prozedur kommt trotz der „MU-heit“ihrer Schleifen schließlich zu einem Halt, was immer der Input sein mag. Eine nichtendende Prozedur geht immer weiter, für mindestens eine Wahl des Inputs. Wenn wir durch eine komplizierte Prüfung