Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

GEB - Diagram G recurive definition

  1. Sep 1, 2008 #1
    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
     
  2. jcsd
  3. Sep 1, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  4. Sep 1, 2008 #3
    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
     
  5. Sep 1, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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))
     
  6. Sep 1, 2008 #5

    Integral

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
    Last edited: Sep 1, 2008
  7. May 26, 2010 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: GEB - Diagram G recurive definition
  1. Limits and .9 recurring (Replies: 24)

  2. GEB question (Replies: 3)

Loading...