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

Recursive Trees (from GED)

  1. Aug 2, 2006 #1
    In chapter five of Douglas Hofstadter's book Goedel, Escher, Bach, the author poses a question about recursively-defined trees:
    I've been trying to solve it today, and the only solution I came up with is:
    G(n) = (n+1) - G(G(n-1)+1) for n>4
    G(O) = 0, G(1) = 1, G(2) = 2, G(3) = 3, G(4) = 3 (hope i remember it well),
    which is apparently not as elegant as the original definition. Has anyone of you come up with a better solution? Or is there any general method (procedure) how to transform recursive algebraic definition of trees into recursive algebraic definitions of "flip-trees"?
  2. jcsd
  3. Aug 2, 2006 #2
    Doesnt it have something to do with odd and even numbers, a bit like the trigonometric functions of the tayor series?
  4. Aug 2, 2006 #3
    I'm not sure about that... I'll try to state the whole problem:

    Having a recursive algebraic definition of a function F(n), one can construct a tree by placing n-nodes above F(n)-nodes:

    Code (Text):
                             (4)        (5)
                              |          |
                              ----(2)-----           (3)
                                   |                  |
    For this particular tree, these equations hold:

    The tree in the book is described by the equation:
    G(n) = n - G(G(n-1)) for n>0
    G(0) = 0

    And the problem is following: imagine you flip the tree around as if in a mirror and relabel all the nodes so they increase from left to right. What would be the recursive algebraic definition for this mirrored tree?

    The solution I came up with is mentioned in my previous post... But apparently it lacks the original elegance - in order to be suitable for the tree, it has to be given five initial values. The original "unmirrored" tree used only one predefined value.
  5. Jul 8, 2009 #4
    I came to the same result this day (actually I gave even more initial values, but my recurrence relation was the same). But I have the same two problems with it: The solution is really unhandy and everything but elegant... Ant at second it still is only an assumption. Unfortunately I have absolutely no clue how it could be shown that this recurrence relation fits to the tree (and it is not even easy to falsify: Calculating high G-flip(n) is okay but having a look at the 2000th level of this weird tree is not that easy...).

    So now my question: Were there any new discoveries in the past few years? Is there any elegant form now or does anyone of you have an idea?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook