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

Folgen
    Unendliche geometrische Strukturen lassen sich in eben dieser Weise definieren, d. h. durch die Expansion eines Knotens nach dem anderen. Definieren wir z. B. ein unendliches Diagramm, nennen wir es „Diagramm G“. Zu diesem Zwecke wählen wir eine implizite Darstellung. In zwei Knoten schreiben wir lediglich den Buchstaben „G“, der jedoch für eine vollständige Kopie von Diagramm G steht. In Abb. 29a ist Diagramm G

Abb. 29 .
a) Diagramm G, nicht erweitert.
c) Diagramm H, nicht erweitert.
b) Diagramm G, einmal erweitert.
d) Diagramm H, einmal erweitert.
    implizit wiedergegeben. Wenn wir Diagramm G jetzt expliziter anschauen wollen, expandieren wir beide G, d. h. wir ersetzen sie durch dasselbe Diagramm, nur in kleinerem Maßstab (Abb. 29b). Diese Version „zweiter Ordnung“ von Diagramm G läßt uns ahnen, wie das endgültige, unmöglich zu realisierende Diagramm G wirklich aussieht. Abb. 30 zeigt einen größeren Teil von Diagramm G, wobei alle Knoten von unten nach oben und von links nach rechts numeriert worden sind. Zwei zusätzliche Knoten — Nr. 1 und Nr. 2 — sind unten hinzugefügt worden.

    Abb. 30 . Diagramm G, noch mehr erweitert und mit numerierten Knoten.
    Dieser unendliche Baum besitzt einige sehr merkwürdige mathematische Eigenschaften. Am rechten Rand nach oben läuft die berühmte Folge der Fibonacci-Zahlen:
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
    die um das Jahr 1202 von Leonardo von Pisa, dem Sohn des Bonaccio (ergo „filius Bonacci“, oder abgekürzt „Fibonacci“) entdeckt wurden. Diese Zahlen werden am besten durch das folgende Formelpaar definiert:
FIBO( n ) = FIBO( n -1) + FIBO( n -2)
für n > 2
FIBO(1) = FIBO(2) = 1
    Man beachte, wie diese Fibonacci-Zahlen vermittels vorhergehender Fibonacci-Zahlen definiert werden. Wir könnten dieses Formelpaar in einem RTN darstellen (Abb. 31):

    Abb. 31 . Ein RTN für Fibonacci-Zahlen.
    So kann man also FIBO(15) durch eine Reihe rekursiver Aufrufe der durch das obige RTN definierten Prozedur definieren. Diese rekursive Definition läuft aus, wenn man auf FIBO(1) oder FIBO(2) stößt (die explizit gegeben sind), nachdem man den Weg rückwärts durch absteigende Werte von n zurückgelegt hat. Den Weg zurückzugehen hat etwas Unhandliches, wenn man genausogut vorwärts gehen könnte, indem man mit FIBO(1) und FIBO(2) beginnen und fortwährend die beiden Werte addieren würde, bis man FIBO(15) erreicht. Auf diese Weise muß man nicht auf einen Stapel achten.
    Nun hat Diagramm G sogar noch überraschendere Eigenschaften als diese. Seine gesamte Struktur kann in einer einzigen rekursiven Definition codiert werden, und zwar:
G( n ) = n - G(G( n -1))
für n > 0
G(0) = 0
    Wie läßt sich diese Funktion G( n ) als Baumstruktur codieren? Ganz einfach, wenn man einen Baum konstruiert, indem man G( n ) für alle Werte von n unter n setzt, wird man das Diagramm G neu schaffen. Tatsächlich habe ich Diagramm G zuerst auf diese Weise entdeckt. Ich untersuchte die Funktion G, und als ich versuchte, ihre Werte rasch zu berechnen, verfiel ich darauf, die Werte, die ich bereits kannte, in Baumform anzuordnen. Zu meiner Überraschung erwies sich, daß der Baum eine äußerst wohlgeordnete rekursive geometrische Darstellung besaß.
    Wenn man einen analogen Baum für eine Funktion H( n ) erzeugt, die durch genau eine Verschachtelung mehr als G definiert ist —
H( n ) = n - H(H(H( n - 1)))
für n > 0
H(0) = 0
    — dann ist noch erstaunlicher, daß das zugehörige „Diagramm H“ wie in Abb. 29c implizit definiert ist. Der rechte Ast enthält einen zusätzlichen Knoten, aber das ist der einzige Unterschied. Die erste rekursive Expansion von Diagramm H zeigt Abb. 29d. Und so geht es weiter — für jeden Verschachtelungsgrad. Diese rekursiven geometrischen Strukturen, die genau den rekursiven algebraischen Definitionen entsprechen, sind von schöner Regelmäßigkeit.
    Ein Problem für neugierige Leser: angenommen man dreht das Diagramm G herum wie in einem Spiegel und etikettiert die Knoten des neuen Baums so, daß sie von links nach rechts ansteigen. Können Sie eine rekursive algebraische Definition für diesen „umgekehrten Baum“ finden? Und wie steht es mit der „Drehung“ des H-Baumes? Und so weiter?
    Ein anderes hübsches Problem betrifft ein Paar von rekursiv miteinander verwickelten Funktionen F( n ) und M( n ) — sozusagen „verheiratete“ Funktionen, definiert wie folgt:
F( n ) = n - M(F( n - 1))
für n > 0
M( n ) = n -