GEB - Diagram G recurive definition

In summary: Hope this helps.In summary, the conversation discusses a recursive function given for Diagram G as well as a way to codify the Fibonacci sequence created by the diagram. There is confusion about the function and its purpose, with the question of how n-(anything) can produce G(n). The response suggests that the OP should go back and re-read the text associated with the diagrams in Godel, Escher, Bach to gain a better understanding. Ultimately, the function is used to create a graph, with each value representing a connection between two numbers. The values for G(0) and G(1) can be ignored for this purpose.
  • #1
dsmith1974
4
0
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
 
Mathematics news on Phys.org
  • #2
dsmith1974 said:
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.
 
  • #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
 
  • #4
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))
 
  • #5
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:
  • #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.
 

What is GEB - Diagram G recursive definition?

GEB - Diagram G recursive definition is a concept introduced in Douglas Hofstadter's book "Gödel, Escher, Bach: An Eternal Golden Braid". It is a way of representing recursive definitions graphically using a technique called "strange loops".

How does GEB - Diagram G recursive definition work?

GEB - Diagram G recursive definition works by representing a recursive definition as a loop within a larger system. Each iteration of the loop adds a new layer of complexity to the overall system, creating a "strange loop" that can be endlessly self-referential.

What is the purpose of using GEB - Diagram G recursive definition?

The purpose of using GEB - Diagram G recursive definition is to visually demonstrate the concept of self-reference and recursion in a more intuitive way. It allows for a better understanding of how recursive definitions can create complex and seemingly paradoxical systems.

Can GEB - Diagram G recursive definition be applied to real-world problems?

Yes, GEB - Diagram G recursive definition can be applied to real-world problems in fields such as computer science, mathematics, and philosophy. It can help in understanding and solving problems that involve self-referential and recursive processes.

Are there any limitations to GEB - Diagram G recursive definition?

While GEB - Diagram G recursive definition is a useful tool for visualizing recursive definitions, it may not always accurately represent the complexity of a real-world problem. It is important to use critical thinking and analysis in conjunction with GEB - Diagram G to fully understand and solve a problem.

Similar threads

  • General Math
4
Replies
125
Views
16K
  • Math Proof Training and Practice
Replies
23
Views
3K
  • General Math
Replies
1
Views
4K
  • Math Proof Training and Practice
6
Replies
175
Views
19K
  • General Math
Replies
10
Views
9K
  • Quantum Physics
Replies
4
Views
5K
  • Linear and Abstract Algebra
Replies
3
Views
6K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
4K
  • Linear and Abstract Algebra
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
Back
Top