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

den Knoten Ende, was auf Herauspoppen hinausläuft, und so gehen wir zu unserem Stapel, um die Return-Adresse zu finden. Er sagt uns, daß wir inmitten der Ausführung von FANTASIEVOLLES SUBSTANTIV eine Stufe höher waren — und so setzen wir dort wieder ein. Das ergibt „die purpurfarbene Kuh ohne Hörner“.
    Auch auf dieser Stufe stoßen wir auf Ende, und so poppen wir noch einmal auf eine höhere Stufe, diesmal brauchen wir ein VERBUM . Nehmen wir „ verschlang “. Das beendet den Aufruf von FANTASIEVOLLES SUBSTANTIV auf der höchsten Stufe, mit dem Ergebnis, daß der Ausdruck
    „ die seltsamen Krapfen, die die purpurfarbene Kuh ohne Hörner verschlang“ “
    nach oben zu dem geduldigen SATZ weitergeleitet wird, wenn wir ein letztes Mal poppen.
    Wie man sieht, geraten wir nicht in eine unendliche Regression. Der Grund ist der, daß zumindest eine Bahn innerhalb des RTNs FANTASIEVOLLES SUBSTANTIV keinen rekursiven Aufruf von FANTASIEVOLLEM SUBSTANTIV selbst bedingt. Natürlich hätten wir uns widersinnigerweise darauf versteifen können, immer die untere Bahn innerhalb FANTASIEVOLLEM SUBSTANTIV zu wählen, und dann wären wir nie zu einem Ende gekommen, genauso wie das Akronym Z EUS nie völlig entwickelt werden konnte. Wenn aber die Bahnen rein zufällig gewählt werden, kann eine unendliche Regression dieser Art nie zustande kommen.
„Auslaufen“ und Heterarchien
    Das ist die entscheidende Tatsache, durch die sich rekursive Definitionen von zirkulären unterscheiden. Es gibt immer einen Teil der Definition, der Selbstbezüglichkeit vermeidet, so daß die Konstruktion eines Objekts, das der Definition genügt, schließlich „ausläuft“.
    Nun gibt es auch indirektere Methoden als den Selbstaufruf, um Rekursivität in RTNs zu erreichen. Da wäre etwa die Analogie zu Eschers Zeichnen ( Abb. 135 ), wo jede der beiden Prozeduren eine andere aufruft, aber nicht sich selbst. Z. B. könnten wir ein RTN namens NEBENSATZ haben, das FANTASIEVOLLES SUBSTANTIV aufruft, wann immer ein Objekt für ein transitives Verbum benötigt wird, und umgekehrt könnte der obere Weg von FANTASIEVOLLES SUBSTANTIV RELATIVPRONOMEN aufrufen und dann NEBENSATZ , wann immer ein Relativsatz benötigt wird. Das ist ein Beispiel für indirekte Rekursivität und erinnert auch an die zweistufige Version der Paradoxie von Epimenides.
    Es braucht nicht eigens gesagt zu werden, daß es ein Triplett von Prozeduren geben kann, die sich alle gegenseitig zyklisch aufrufen usw. Es kann ganze Familien von RTNs geben, die alle miteinander verwickelt sind und sich selber und die anderen wie verrückt aufrufen. Ein Programm mit einer solchen Struktur, in der es keine „höchste Stufe“ (oder keinen „Monitor“) gibt, nennt man eine Heterarchie (im Gegensatz zu Hierarchie). Der Ausdruck stammt, glaube ich, von Warren McCulloch, einem der ersten Kybernetiker und einem hingabevollen Erforscher von Gehirnen und Denkprozessen.
Knoten, die sich ausdehnen
    Anschaulich läßt sich wie folgt über RTNs nachdenken: Wann immer man sich auf einem Weg bewegt und auf einen Knoten stößt, der ein RTN aufruft, dann „expandiert“ man den Knoten, d. h. man ersetzt ihn durch eine sehr kleine Kopie des RTNs, das er aufruft (s. Abb. 28). Dann geht man weiter, in dieses winzige RTN hinein! Wenn

    Abb. 28 . Das RTN FANTASIEVOLLES SUBSTANTIV mit einem rekursiv erweiterten Knoten.
    man aus ihm herauspoppt, ist man im großen Knoten automatisch am richtigen Ort. Während man sich im kleinen aufhält, kommt man möglicherweise dazu, sogar noch weitere Miniatur-RTNs zu konstruieren. Wenn man aber Knoten nur dann expandiert, wenn man auf sie stößt, vermeidet man die Notwendigkeit der Herstellung eines unendlichen Diagramms, selbst wenn ein RTN sich selbst aufruft.
    Einen Knoten zu expandieren, ist nicht ganz unähnlich der Substitution eines Buchstabens in einem Akronym durch das Wort, das es repräsentiert. Das Akronym Z EUS ist rekursiv, hat aber den Nachteil — oder den Vorzug —, daß man das Z immer wieder expandieren muß; es läuft also nie aus. Wenn jedoch das RTN als ein wirkliches Computerprogramm verwendet wird, dann gibt es zumindest einen Weg, der direkte Rekursivität vermeidet, so daß keine unendliche Regression entsteht. Selbst die heterarchischste Programmstruktur läuft aus — sonst würde sie nicht funktionieren! Sie würde nur ständig einen Knoten nach dem anderen expandieren, aber nie eine Handlung ausführen.
Diagramm G und rekursive