| 29.07.2005, 12:29 |
-felix- |
Auf diesen Beitrag antworten » |
Diagramm G aus "Gödel Escher Bach"
Hallo,
ich bin gerade dabei, das Buch "Gödel Escher Bach" von Hofstadter zu lesen und hänge gerade im Kapitel Rekusion fest. Dort wird das Diagramm G wie folgt beschrieben:
| Zitat: |
Unendliche geometrische Strukturen lassen sich in eben dieser Weise definieren, d.h. durch die Expansion eines Kontens 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 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 sind. Zwei zusätzliche Knoten - Nr. 1 und Nr. 2 - sind unten hinzugefügt worden.
Dieser unendliche Baum besitzt einige sehr merkwürde mathematische Eigenschaften. Am rechten Rand nach oben läuft die berühmte Folge der Fibonacci-Zahlen: [..., es folgt ein Abschnitt über Fibonacci-Zahlen]
Nun hat Diagramm G sogar noch überraschendere Eigenschaften als diese. Seine gesamte Struktur kann in einer einzigen rekursiven Definition codiert werden, und zwar:
Wie läßt sich diese Funktion als Baumstruktur codieren? Ganz einfach, wenn man einen Baum konstruiert, indem man für alle Werte von unter 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 Darstellung besaß. |
Ich verstehe, wie ich das Diagramm G rekursiv zeichnen kann, ich verstehe aber nicht die Verbindung zwischen der Funktion und dem Diagramm, also was mit
| Zitat: |
| Ganz einfach, wenn man einen Baum konstruiert, indem man für alle Werte von unter setzt, wird man das Diagramm G neu schaffen. |
gemeint ist.
Ich habe noch eine Wertetabelle von G(n) erstellt, vielleicht hilft das jemand weiter:
|
Also, angenommen n=1, dann ist n-1=0 und G(0):=0 ist als Startwert vordefiniert.
G(1)=1-G(G(0)) = 1-G(0) = 1-0 = 1.
Jetzt n=2:
G(2)=2-G(G(1)) = 2-G(1) = 2-1 = 1.
G(3)=3-G(G(2)) = 3-G(1) = 3-1 = 2.
G(4)=4-G(G(3)) = 4-G(2) = 4-1 = 3.
G(5)=5-G(G(4)) = 3-G(3) = 5-2 = 3.
....
Der Zusammenhang zum Graphen ist der, dass (ausser der 1) bedeuten alle Zahlen die doppelt vorkommen, wie z.B. die 3, dass bei ihrem Knotenpunkt eine Verzweigung in 2 Äste geschieht, während bei denen die nur einmal vorkommen, es nur in eine Richtung weitergeht.
mfg, phi. |
