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

F(M( n - 1))
F(0) = 1, und M(0) = 0
    Die RTNs dieser beiden Funktionen rufen einander und ebenfalls sich selber auf. Das Problem besteht einfach darin, die rekursiven Strukturen von Diagramm F und Diagramm M herauszufinden. Sie sind einfach und elegant.
Eine chaotische Folge
    Ein letztes Beispiel von Rekursion in der Zahlentheorie führt zu einem kleinen Mysterium. Betrachten wir die folgende rekursive Definition einer Funktion
Q( n ) = Q( n - Q( n - 1)) + Q( n - Q( n - 2))
für n > 2
Q(1) = Q(2) = 1.
    Sie erinnert an die Fibonacci-Definition, indem jeder neue Wert die Summe zweier vorhergehender Werte ist — aber nicht der unmittelbar vorhergehenden Werte. Statt dessen sagen uns die zwei unmittelbar vorhergehenden Werte, wie weit wir rückwärts zählen müssen, um die Zahlen zu erhalten, die wir addieren müssen, um den neuen Wert zu erhalten. Die ersten 17 Q-Zahlen lauten wie folgt:
1,  1,  2,  3,  3,  4,  5,  5,  6,  6,  6,  8,  8,  8,  10,  9,  10, ...
1,  1,  2,  3,  3,  4,  5,  ↑ ,  ↑ ,  6,  6,  8,  8,  8,  10
1,  1,  2,  3,  3,  4,  5,  5 + 6 = 11   8,  8,  8,  10 um soviel
1,  1,  2,  3,  3,  4,  5,   5 +     nach links weiterrücken
1,  1,  2,  3,  3,  4,  5,  5, neuer Term
 
    Um die nächste zu erhalten, geht man (von den drei Punkten aus) 10 bzw. 9 Terme nach links; man erreicht eine 5 und eine 6, wie die Pfeile zeigen. Ihre Summe — 11 gibt den neuen Wert: Q(18). Dies ist das seltsame Vorgehen, bei dem die Liste der bekannten Q-Zahlen dazu verwendet wird, sich selbst zu verlängern. Die so erzeugte Folge ist, gelinde gesagt, zumindest absonderlich. Je weiter man geht, desto weniger Sinn scheint sie zu haben. Das ist einer jener sehr absonderlichen Fälle, wo etwas, das wie eine einigermaßen natürliche Definition aussieht, zu äußerst rätselhaftem Verhalten führt — zu einem auf sehr ordentliche Art und Weise herbeigeführten Chaos. Man fragt sich natürlich, ob das vermeintliche Chaos irgendeine subtile Regelmäßigkeit enthält. Natürlich besteht definitionsgemäß Regelmäßigkeit; interessant ist aber, ob es eine andere Möglichkeit gibt, diese Folge zu charakterisieren — und das, wenn man Glück hat, auf nicht-rekursive Art und Weise.
Zwei eindrucksvolle rekursive Graphen
    Die Wunder der Rekursion in der Mathematik sind nicht zu zählen, und ich beabsichtige nicht, sie alle vorzuführen. Doch kenne ich ein paar besonders eindrucksvolle Beispiele aus meiner eigenen Erfahrung, die mir erwähnenswert erscheinen. Beide sind Graphen. Das eine Beispiel tauchte im Verlauf gewisser zahlentheoretischer Untersuchungen auf, das andere im Verlauf meiner Dissertation auf dem Gebiet der Festkörperphysik. Das wirklich Faszinierende daran ist, daß die beiden Graphen eng miteinander verwandt sind.

    Abb. 32 . Graph der Funktion INT(x). Bei jedem rationalen Wert von x gibt es einen Diskontinuitätssprung.
    Der erste (Abb. 32) ist ein Graph einer Funktion, die ich INT( x ) nenne. Er ist hier für x zwischen 0 und 1 dargestellt. Für x zwischen jedem anderen Paar von ganzen Zahlen, n und n+1 ermittelt man einfach INT( x−n ), und addiert dann n. Die Struktur der Darstellung ist, wie man sieht, recht sprunghaft. Sie besteht aus einer unendlichen Anzahl von gekrümmten Stücken, die gegen die Ecken hin immer kleiner werden und übrigens auch immer weniger stark gekrümmt. Wenn man nun jedes solche Teilstück genau betrachtet, wird man feststellen, daß es tatsächlich eine Kopie des ganzen Graphs ist — lediglich gekrümmt! Die sich daraus ergebenden Implikationen sind phantastisch. Eine davon ist die, daß der Graph von INT lediglich aus Kopien seiner selbst besteht, die bis in eine unendliche Tiefe ineinander verschachtelt sind.
    Wenn man ein beliebiges Teilstück des Graphs, so klein es auch sein möge, herausnimmt, hält man eine vollständige Kopie des ganzen Graphs in Händen — ja unendlich viele Kopien von ihm.
    Die Tatsache, daß INT aus nichts als aus Kopien seiner selbst besteht, könnte zur Ansicht verleiten, daß es zu flüchtig ist, um existieren zu können. Seine Definition sieht zu zirkulär aus. Wie kann es sich jemals vom Boden erheben? Eine sehr interessante Angelegenheit. Vor allem ist festzustellen, daß es bei der Beschreibung von INT für jemand, der es nicht gesehen hat, nicht genügt, einfach zu sagen: „Es besteht aus Kopien seiner selbst.“ Die andere Hälfte der Angelegenheit — die nicht-rekursive Hälfte — sagt