Godel Escher Bach e diagramma G

[pippo931]

Salve a tutti, sto leggendo "Godel, Escher, Bach", sono arrivato al capitolo V e non mi sono chiare due cose:

Quando parla del diagramma G e dice che è regolato dalle funzioni: $G(n)=n-G(G(n-1))$ per $n>0$ e $G(0)=0$ non capisco cosa intenda con $G(n)$.

Poi, a pag.147 disegna il diagramma G con espansioni e i nodi numerati, nel lato destro compare la successione di Fibonacci, perchè?

PS: non so se questa sia la sezione giusta, i moderatori, sicuramente più esperti di me, spostino pure il messaggio

Grazie mille in anticipo

[orazioster]

se la tua funzione è $G(n)={(0, text{se} n=0), (n-G(G(n-1)), text{altrimenti}):}$, $ninNN$;
è questa . ! intendo che la funzione è proprio quella, come è a quel modo definita (non so cosa dicesse il testo. Il libro l'ho letto tanti anni fa!).

La successione di Fibonacci:
$F(n) ={(1, text{se} n=0),(1, se n=1), (F(n-1) + F(n-2), text{altrimenti}):}$, $ninNN$.

[pippo931]

poiché non ho trovato un chiarimento nelle parole di orazioster aggiungo un link del libro (in inglese, in italiano non l'ho trovato): http://www.scribd.com/doc/7040352/Godel ... lden-Braid . Il capitolo in questione inizia a pag.143, la funzione viene descritta a pag. 145 (seguendo la numerazione non elettronica, quella reale del libro).

Inoltre cerco di riformulare la domanda: in che modo un diagramma può essere regolato da funzioni e cosa rappresenta $G(n)$ nel diagramma?

Grazie

[orazioster]

Ho guardato le pagine.
Quando posso, vedrò come è realizzato uno di quei diagrammi, chiamati nel testo RTN.

Se la funzione G è quella che si era scritto:

$G(n) ={(0, text{se n}=0),(n -G(G(n-1)), text{altrimenti}):}$, $ninNN$.

le immagini sono
(ho corretto il mio precedente messaggio chè non le avevo ben calcolate)

G(0)=0,
G(1)=1-G(G(0))= 1 -G(0) =1-0=1
G(2)=2-1=1
G(3)=3 -1=2
G(4)= 4- 1 =3
G(5)= 5-2=3
G(6)=6-2=4
G(7)=7-2=5
...
Ah! un pari pare apparire una volta nelle immagini, ed il dispari successivo le due successive, poi il pari successivo...

I numeri di Fibonacci c'entrano con quel diagramma perchè sono i numeri dei nodi all' estrema destra. Ovvero
nella "riga" n diverso da 0, contando le "righe" ordinatamente in su partendo da 0, hai come numero di nodi l'n-esimo numero di F. .
E puoi ripetere mutatis mutandis questo discorso per ogni diramazione.

[pippo931]

problema risolto... si trattava di una semplice incomprensione

[orazioster]

._

Leggendo quando ne ho avuto agio il testo, ho
letto Hofstadter che diceva: "basta metter G(n) sotto n". ...E così, ho capito.
Ora provo a disegnare qui il grafico.

*_*__*__*_*___*_*___*__
*1*__2__*3*___*5*___4__
_*___*___*_____*____*__
_*___*_ _*______*___*__
_**1**__ 2______**3**__
___*_____*________*____
___*_____*________*____
___***1***________2____
______*___________*____
______*___________*____
______*******1*****____
______________*_________
______________*_________
______________1_________

[orazioster]

Infatti, ogni "riga" ha numero di nodi
1,1,2,3,5,8,... $F_n$, n-esimo numero del "Figlio di Bonaccio".

[Topezio]

volevo solo dirvi che le immagini non sono quelle che avete scritto, in particolare:
G(7)=4
G(8)=5
G(9)=6
G(10)=6
G(11)=7
G(12)=8
G(13)=8
G(14)=9
G(15)=9 etc. etc.

quindi la regolarità pari e dispari di cui parla Orazioster non è del tipo che ipotizza...

per avere un buon grafico, nel senso in cui ne parla Hofstadter provate a riportare in riga alcuni valori di n, per esempio da 1 a 8;
fatto ciò iniziate a riportare nella riga immediatamente successiva i valori G(n) corrispondenti, avendo cura di riportarne uno solo per ciascuna coppia del livello superiore da cui provengono;
congiungendo con una struttura ad albero e ripetendo il procedimento per la riga successiva avrete il vostro 'diagramma G'


'quaerendo invenietis'

[Il Pitagorico]

Scusatemi, a me non mi è ancora chiaro come si costruisce il diagramma G.