Thread: Infinite diagram G

Could you post the page number, assuming you have the 20th anniversary edition?

N
| - - - |
n1- - n2
- | - - |
na,nb nc,nd

Probably?

I think hes talking about recursivity resulting into infinity. Look up recursivity and you will understand Diagram G. I haven't read that book tho, but I'm pretty sure this is what he is talking about.

Out of interest I downloaded the ebook and started reading so I thought I might as well post the diagrams for those who are interested:

I may be wrong, but here's what I think. If you look at the bottom picture ChaybaChayba posted, you see that for each circular node (which corresponds to a given n), there is a line under it leading to another node -- that node is G(n) for that n. Thus, 1 is under 2 so G(2) is 1.

G(n) is not necessarily equal to n -- for example, G(5) = 5 - G(G(4)) = 5 - G(3) = 5 - 2 = 3 and G(21) = 13.

Hopefully I am right and this helps. Amazing book, by the way.

It starts on page 135

Wildman pretty much explained this. It's an example of a recurrence relation and is a way to define a sequence.

This is a pretty cool sequence in that every integer can be written as G(n) for some n and there can only be two such integers n. This means that the tree will have no leafs (i.e. dead ends) and that there will never be more than two branches from a node.



So The proof isn't complete. I'm gonna finish it tomorrow before I live up to my name. My assertions are absolutely correct though.

Spoiler for Proof:

----------------------------------------------------------------------------


Lemma:
1, 0 <= G(n) - G(n - 1) <= 1 for n > 0
2. G(n - 2) < G(n) for n > 1

Proof:
G(1) - G(0) = 1 so we have our base-case. Assume that 0 <= G(m) - G(m - 1) <= 1 for m < n.

Then we have

Code:

G(n) - G(n - 1) = n - GG(n - 1) - n + 1 + GG(n - 2)     (Definition of G)
                = 1 - GG(n - 1) + GG(n - 2)                    EQN1
                = 1 - (GG(n - 1) - GG(n - 2))

and by the inductive hypothesis, G(n - 1) = G(n - 2) or G(n - 1) = G(n - 2) + 1.

Assume the former. Then GG(n - 1) - GG(n - 2) = 0 and so G(n) - G(n - 1) = 1. This suffices to show part 1 for this case. Then G(n) - G(n - 2) = [G(n) - G(n - 1)] + [G(n - 1) - G(n - 2)] = 1 + 0, and part 2 holds.

Consider the case where G(n - 1) - G(n - 2) = 1. Then G(n) - G(n - 2) = [G(n) - G(n - 1)] + [G(n - 1) - G(n - 2)] = G(n) - G(n - 1) + 1.
■



Proposition:
1) For all m > 0, there exists at least one n >= 0 such that G(n) = m.

2) There exist at most two such n for any given m.

Proof:
Assume that there exists m such that there is no n with G(n) = m and that it is the
least such m. Then there exists an n such that G(n) = m - 1. if G(n + 1) = m + 1
then Lemma 4 is violated. So G(n + 1) = m - 1. Take G(n + 2). If G(n + 2) = m + 1,
then, again, Lemma 4 is violated. But now if G(n + 2) = m - 1, Lemma 5 is violated.
We are left with the conclusion that G(n + 2) = m contrary to our assumption that no
such n exists. Hence there must be no such m. So for every m, there exists at least
one n such that G(n) = m.

Now suppose that G(n) = G(n + j) for j > 0. Then G(n + j) - G(n) = 0 which, by lemma 4
and 5 is only possible if j = 0 or j = 1. Hence, only a pair of successive integers can
have the same image under G and there can be at most two such integers.
■

Spoiler for First hundred values:

G(0) = 0 - G(G(-1)) = 0
G(1) = 1 - G(G(0)) = 1
G(2) = 2 - G(G(1)) = 1
G(3) = 3 - G(G(2)) = 2
G(4) = 4 - G(G(3)) = 3
G(5) = 5 - G(G(4)) = 3
G(6) = 6 - G(G(5)) = 4
G(7) = 7 - G(G(6)) = 4
G(8) = 8 - G(G(7)) = 5
G(9) = 9 - G(G(8)) = 6
G(10) = 10 - G(G(9)) = 6
G(11) = 11 - G(G(10)) = 7
G(12) = 12 - G(G(11)) = 8
G(13) = 13 - G(G(12)) = 8
G(14) = 14 - G(G(13)) = 9
G(15) = 15 - G(G(14)) = 9
G(16) = 16 - G(G(15)) = 10
G(17) = 17 - G(G(16)) = 11
G(18) = 18 - G(G(17)) = 11
G(19) = 19 - G(G(18)) = 12
G(20) = 20 - G(G(19)) = 12
G(21) = 21 - G(G(20)) = 13
G(22) = 22 - G(G(21)) = 14
G(23) = 23 - G(G(22)) = 14
G(24) = 24 - G(G(23)) = 15
G(25) = 25 - G(G(24)) = 16
G(26) = 26 - G(G(25)) = 16
G(27) = 27 - G(G(26)) = 17
G(28) = 28 - G(G(27)) = 17
G(29) = 29 - G(G(28)) = 18
G(30) = 30 - G(G(29)) = 19
G(31) = 31 - G(G(30)) = 19
G(32) = 32 - G(G(31)) = 20
G(33) = 33 - G(G(32)) = 21
G(34) = 34 - G(G(33)) = 21
G(35) = 35 - G(G(34)) = 22
G(36) = 36 - G(G(35)) = 22
G(37) = 37 - G(G(36)) = 23
G(38) = 38 - G(G(37)) = 24
G(39) = 39 - G(G(38)) = 24
G(40) = 40 - G(G(39)) = 25
G(41) = 41 - G(G(40)) = 25
G(42) = 42 - G(G(41)) = 26
G(43) = 43 - G(G(42)) = 27
G(44) = 44 - G(G(43)) = 27
G(45) = 45 - G(G(44)) = 28
G(46) = 46 - G(G(45)) = 29
G(47) = 47 - G(G(46)) = 29
G(48) = 48 - G(G(47)) = 30
G(49) = 49 - G(G(48)) = 30
G(50) = 50 - G(G(49)) = 31
G(51) = 51 - G(G(50)) = 32
G(52) = 52 - G(G(51)) = 32
G(53) = 53 - G(G(52)) = 33
G(54) = 54 - G(G(53)) = 33
G(55) = 55 - G(G(54)) = 34
G(56) = 56 - G(G(55)) = 35
G(57) = 57 - G(G(56)) = 35
G(58) = 58 - G(G(57)) = 36
G(59) = 59 - G(G(58)) = 37
G(60) = 60 - G(G(59)) = 37
G(61) = 61 - G(G(60)) = 38
G(62) = 62 - G(G(61)) = 38
G(63) = 63 - G(G(62)) = 39
G(64) = 64 - G(G(63)) = 40
G(65) = 65 - G(G(64)) = 40
G(66) = 66 - G(G(65)) = 41
G(67) = 67 - G(G(66)) = 42
G(68) = 68 - G(G(67)) = 42
G(69) = 69 - G(G(68)) = 43
G(70) = 70 - G(G(69)) = 43
G(71) = 71 - G(G(70)) = 44
G(72) = 72 - G(G(71)) = 45
G(73) = 73 - G(G(72)) = 45
G(74) = 74 - G(G(73)) = 46
G(75) = 75 - G(G(74)) = 46
G(76) = 76 - G(G(75)) = 47
G(77) = 77 - G(G(76)) = 48
G(78) = 78 - G(G(77)) = 48
G(79) = 79 - G(G(78)) = 49
G(80) = 80 - G(G(79)) = 50
G(81) = 81 - G(G(80)) = 50
G(82) = 82 - G(G(81)) = 51
G(83) = 83 - G(G(82)) = 51
G(84) = 84 - G(G(83)) = 52
G(85) = 85 - G(G(84)) = 53
G(86) = 86 - G(G(85)) = 53
G(87) = 87 - G(G(86)) = 54
G(88) = 88 - G(G(87)) = 55
G(89) = 89 - G(G(88)) = 55
G(90) = 90 - G(G(89)) = 56
G(91) = 91 - G(G(90)) = 56
G(92) = 92 - G(G(91)) = 57
G(93) = 93 - G(G(92)) = 58
G(94) = 94 - G(G(93)) = 58
G(95) = 95 - G(G(94)) = 59
G(96) = 96 - G(G(95)) = 59
G(97) = 97 - G(G(96)) = 60
G(98) = 98 - G(G(97)) = 61
G(99) = 99 - G(G(98)) = 61
G(100) = 100 - G(G(99)) = 62

Spoiler for Python code to calculate values:

Code:

 
def G(N):
    values = {0: 0}
    for i in xrange(1, N+1):
        values[i] = i - values[values[i-1]]
    return values

def print_g_to_n(N):
    for n, g in G(N).iteritems():
        print "G({0}) = {0} - G(G({1})) = {2}".format(n, n-1, g)
print_g_to_n(100)

Guys. Hey guys?

Could we...

Could we have a 'G.E.B. General' thread?

Sure. I'm reading it at the moment (I tried and failed a couple of years ago... wasn't intellectually ready) and it's brilliant.

Ok, finally found time to do this. It made me really wish the forum had LaTeX but no such luck. If you actually want to read it, my condolences. It's a little longish but it's broken up into pieces and isn't too difficult. I would think that somebody with the mathematical maturity to handle calculus should be able to handle this (possibly with some questions). There's no calculus or algebra involved, this is completely elementary.

Spoiler for Proof.:

Lemma 1:
0 < G(n) < n for n > 1

Proof:

0 < G(2) = 1 < 2 so we have the base case. By induction, 0 < G(n - 1) < n - 1. We then use induction again and have 0 < GG(n - 1) < G(n - 1) < n. This means that 0 < G(n) = n - GG(n - 1) < n.
■

Lemma 2:
0 <= G(n) - G(n - 1) <= 1 for n > 0

This is equivalent to the saying that G(n+1) = G(n) + 1 or G(n + 1) = G(n).

Proof:
For our base case, we have G(1) - G(0) = 1. Assume inductively that 0 <= G(n - 1) - G(n - 2) <= 1.

We have

G(n) - G(n - 1) = n - GG(n - 1) - n + 1 + GG(n - 2) = 1 - [GG(n - 1) - GG(n - 2)]


By Lemma 1, the inductive hypothesis applies and we can conclude that 0 < G(n - 1) - G(n - 2) <= 1. Then either G(n - 1) = G(n - 2) or G(n - 1) = G(n - 2) + 1. If the former is the case, then GG(n - 1) = GG(n -2) and it follows that G(n) - G(n - 1) = 1. If the latter, then 0 < G(n - 2), G(n - 1) < n by Lemma 1 and the inductive hypothesis holds so that we can conclude that 0 <= GG(n - 1) - GG(n - 2) <= 1. But this just means that 0 <= G(n) - G(n - 1) <= 1 as was to be shown.
■

Corollary of Lemma 2:
if n <= m then G(n) <= G(m)

Proof:
It suffices to show that G(m) - G(n) >= 0. We proceed by induction on m - n. Suppose m - n = 0. Then G(m) - G(n) = 0. For the inductive step, we have G(m) - G(n) = [G(m) - G(m - 1)] + [G(m - 1) - G(n)]. By induction, G(m - 1) - G(n) >= 0 and by Lemma 2, G(m) - G(m - 1) >= 0 and so the corollary holds.
■


Lemma 3:
1 <= G(n) - G(n -2) <= 2 for n > 1

The intuition here is that the function can't have the same value on three integers in a row.

Proof:
We have

G(n) - G(n - 2) = [G(n) - G(n - 1)] + [G(n - 1) - G(n - 2)]


By lemma 2, this can assume 4 states with the two terms on the right hand side each assuming a value of 0 or 1. The only problem is when both are 0. So assume that G(n - 1) - G(n - 2) = 0. Then GG(n - 1) - GG(n - 2) = 0. But as in the proof of Lemma 2, we have G(n) - G(n - 1) = 1 - [GG(n - 1) - GG(n - 2)]. So we see that if the rightmost term is 0, the left term must be 1 and the result holds.
■

Proposition 1:
For all m > 0, there exists at least one n > 0 such that G(n) = m.

This says that the graph is connected in that for every node, we can attach at least one branch to it.

Proof:
We proceed by induction. G(1) = 1. Given m, by induction we have n such that G(n) = m - 1. Take G(n + 1). By Lemma 2, it is either G(n) or G(n) + 1. If it is G(n) + 1 = m, we are done so assume it's G(n). Then again by lemma 1, G(n + 2) is either G(n + 1) or G(n + 1) + 1. But we've assumed that G(n + 1) = G(n). Applying Lemma 3, we see that G(n + 2) is G(n) + 1 or G(n) + 2. The only possibility that both Lemma 2 and Lemma 3 allow is that G(n + 2) = G(n) + 1 = m and our proof is complete.
■

Proposition 2:
Given m > 0, there exist at most two n > 0 such that G(n) = m.

This says that there can be at most two branches on any node.

Proof:
Suppose that G(n + j) = G(n) for j > 0. Then by the corollary of Lemma 2, G(n + i) = G(n) for all 0 < i < j. But by Lemma 3, G(n + 2) > G(n) and we conclude that j = 1.
■

Yeah, I've read past this page now. It's really quite simple compared to some of the preceding stuff. Basically, if you pick a node, and work out G for that node, that value will be below that node.

I understand this now, I think I'm just really out of practice with math, does anyone know of any websites where I can get some algebra problems with solutions? I feel like I've forgotten everything from high school math.

philosopherstoned, that link in your sig is hillarious.

I'm sure a quick Google will get you a good site.

I don't think you need to know much or any algebra to comprehend the book though.

Did you mess around with the hyphen systems he made, though? That's more important I think, but it doesn't require maths as such, just basic reasoning.

I did, I understood how the diagram functioned right away, I just got confused when I started messing with the equation. I understand the book fine, I just used to be good with math and equations and am not at all anymore.

For what it's worth, there's not a lot of algebraic manipulation to be done with the recurrence relation. The fact that these things are recursive means that when you try to do algebra with them, you first have to expand out one side. But then... surprise! You have to expand it out again because it's defined in terms of itself. ad infinitum.

You'll note that when I was playing with it, I didn't solve for much of anything. For example, to conclude that

G(n) - G(n - 2) = [G(n) - G(n - 1)] + [G(n - 1) + G(n - 2)]

I just wrote

G(n) - G(n - 2) = G(n) - G(n - 2)

and added zero to the right hand side. Just remember that with addition, one can distribute parenthesis however one wants so long as sign changes are taken into account. So the right part could be written

G(n) - [G(n - 1) - G(n - 1)] - G(n - 2)

But

G(n - 1) - G(n -1)

is pretty plainly zero! One learns tricks like that by writing and reading proofs, not by studying basic high school "mathematics".

Ad baseum, more like.

Well, Hofstadter's pretty keen to stress that at this point, anyway.

Originally Posted by stonedape

does anyone know of any websites where I can get some algebra problems with solutions? I feel like I've forgotten everything from high school math.

Try this:

Khan Academy

Yeah, ad baseum is definitely right. I'm not much on latin. It honestly might as well be ad infinitum for the simple reason that it's a huge pain in the ass to deal with one of these things fully expanded. ugghhh.

EDIT:

Of course the distinction between the two is that in a proof, one could possibly use the fact that it can be expanded to G(0) without actually doing so.

Actually as far as I'm aware ad baseum is something I made up, ha. I'm sure there's a proper term for it but... yeah, dead language and all.

The Khan Academy is good, good call.