Goodstein Sequences (Its his 100th birthday!)

LANCE: Bill, on Dec 15, 2012 it will be
Reuben Goodstein's
100th birthday.

BILL: Is he still alive? Will there be a conference in his honor? Free Food? Cake?

LANCE: No, no, and no. But you could blog about Goodstein sequences. (thinking: or they could just look it up here).

BILL: That is a Goodstein idea. You have a Goodstein sequence of good ideas.

I first define a sequence that is not a Goodstein sequence but will be good for education. Let n be a number. Say let n=42 Base 10. We then decrease the number by 1 but increase the base by one. We keep doing this. We get

1. 42 base 10 = 42 base 10
   
2. 41 base 11 = 45 base 10
   
3. 40 base 12 = 48 base 10
   
4. 3E base 13 = 50 base 10 (E stands for Eleven)
   
5. 3T base 14 = 52 base 10 (T stands for Ten)
   
6. 39 base 15 = 54 base 10
   

The sequence looks like its increasing. But note that it eventually gets to

1. 30 base 24 = 72 base 10
   
2. 2(23) base 25 = 73 base 10 (the ``units digit'' is 23)
   
3. 2(22) base 26 = 74 base 10
   

OH MY. Its still increasing. But note that it eventually gets to

1. 20 base 48 base 10 = 96 base 10
   
2. 1(47) base 49 = 96 base 10
   
3. 1(48) base 50 = 98 base 10
   
4. 1(47) base 51 = 98 base 10
   

It seems to be at 98 for a while. Indeed we eventually get to

1. 11 base 97 = 98 base 10
   
2. 10 base 98 = 98 base 10
   
3. 0(97) base 99 = 97 base 10
   

And from there on it it goes to 0. Given n, how many iterations do you need to get to 0? This function grows rather fast, but not THAT fast. To prove that it goes to 0 you need (I think) an induction on an omega-squared ordering. The true Goodstein sequences initially write the number in base 10 but also writes the exponents in base 10 and does that as far as it can: 4 x 10^{2 x 104 + 8 x 103 + 7 x 102} + 8 x 10^{2 x 101 + 3 x 100}

(This is called Hereditary 10 notation.) At each iteration we subtract 1 and then turn all of the 10's into 11's. More generally we write the number in base b and the exp in base b... etc and then subtract 1 and make all of the b's into b+1's. This sequence also goes down to 0. NOW how long does it take to goto 0. The function is not primitive recursive. Also, the theorem that states the sequence eventually goes to 0, cannot be proven in Peano Arithmetic.

I use Goodstein sequences as an example of a natural (one can debate that) function that is not primitive recursive. Ackermann's function comes up more often (lots more often) but is harder to initially motivate.

So Reuben Goodstein, wherever you are, I salute you!