GEB - Diagram G recurive definition

[dsmith1974]

I've been reading Godel, Escher and Bach. In chapter V 'Recursive Structures and Processes' there's a recursive function given for Diagram G as:

G(n) = n - G(G(n-1)) // for n > 0
G(0) = 0

I can codify the Fibonacci seq that the diagram creates as:

$f=1,1;foreach($n in 3..30){$f += $f[$n-2] + $f[$n-3]}

or say that the total node count for rows up to n will be the actual node count on row n+2.

But, I'm not sure what he's trying to say with the function above? I gather it's more a statement about the overall geometric structure rather than an individual item in the Fib. seq.

But how can n - (anything) produce G(n)? Is n an integer - the nth order, or the whole diagram?

Many thanks,

Duncan

 

[HallsofIvy]

I've been reading Godel, Escher and Bach. In chapter V 'Recursive Structures and Processes' there's a recursive function given for Diagram G as:

G(n) = n - G(G(n-1)) // for n > 0
G(0) = 0

I can codify the Fibonacci seq that the diagram creates as:

$f=1,1;foreach($n in 3..30){$f += $f[$n-2] + $f[$n-3]}

or say that the total node count for rows up to n will be the actual node count on row n+2.

But, I'm not sure what he's trying to say with the function above? I gather it's more a statement about the overall geometric structure rather than an individual item in the Fib. seq.

But how can n - (anything) produce G(n)? Is n an integer - the nth order, or the whole diagram?

Many thanks,

Duncan

Since G(0)= 0. G(1)= 1- G(G(0))= 1- G(0)= 1
G(2)= 1- G(G(1))= 1- G(1)= 1- 1= 0
G(3)= 1- G(G(2))= 1- G(0)= 1
G(4)= 1- G(G(3))= 1- G(1)= 0

In other words, G(n) is 0 for any even n, 1 for any odd n.

 

[dsmith1974]

I think (maybe) what he's saying is that for any item g(n), the value will be the sum of all previous items excluding n-1. The notation's a little unclear, but the G(G(n-1)) part is repeated until n=1.

So for e.g.

5 = 2 + 1 + 1 + 1 (skipping 3)
8 = 3 + 2 + 1 + 1 + 1 (skipping 5)
13 = 5 + 3 + 2 + 1 + 1 +1 (skipping 8)
.
.
.

Regards,

Duncan

 

[HallsofIvy]

That doesn't look to me at all like what the OP said but I now notice that I misread it.

For some reason I read it as G(n)= 1- G(G(n-1)) but I now see that it should be G(n)= n- G((G(n-1))

 

[Integral]

I think the OP needs to go back to GEB and re-read the text associated with these diagrams. Hofstadter explains the meaning of that function. Without his text, which the OP did not provide in this post, there is simply NO way anyone can answer this question.

Dsmith1976,
GEB is not something that can be read like a novel, it often requires re-reading sections until you understand. You need to re-read this section ( I have it open in front of me) D.H. tells you the meaning and intent of that function.

 

[acheong87]

Recall the problem.

G(n) = n - G(G(n-1))​

G(0) = 0​

Try it!

G(0) = 0
G(1) = 1 - G(G(0)) = 1 - G(0) = 1 - 0 = 1
G(2) = 2 - G(G(1)) = 2 - G(1) = 2 - 1 = 1
G(3) = 3 - G(G(2)) = 3 - G(2) = 3 - 1 = 2
G(4) = 4 - G(G(3)) = 4 - G(2) = 4 - 1 = 3
G(5) = 5 - G(G(4)) = 5 - G(3) = 5 - 2 = 3
G(6) = 6 - G(G(5)) = 6 - G(3) = 6 - 2 = 4
G(7) = 7 - G(G(6)) = 7 - G(4) = 7 - 3 = 4
G(8) = 8 - G(G(7)) = 8 - G(4) = 8 - 3 = 5
G(9) = 9 - G(G(8)) = 9 - G(5) = 9 - 3 = 6​

Now, how does this become a graph? It's not very obvious. It took me a few hours of trial-and-error. First, let me rewrite the above without the derivations:

G(0) = 0
G(1) = 1
G(2) = 1
G(3) = 2
G(4) = 3
G(5) = 3
G(6) = 4
G(7) = 4
G(8) = 5
G(9) = 6​

Ignore G(0) and G(1) for now.

Start with "G(2) = 1"--interpret this as "2 is connected to 1". Next, "G(3) = 2"--interpret this as "3 is connected to 2". Then, we have both "G(4) = 3" and "G(5) = 3"--interpret these as "4 and 5 are connected to 3".

And so on. If you draw it out, you'll reproduce Diagram G. As for G(0) and G(1)--interpret these as "0 is connected to 0" and "1 is connected to 1"--in other words, they're not really connected to the anything else, so you can ignore them for your purposes.