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

- 42 base 10 = 42 base 10

- 41 base 11 = 45 base 10

- 40 base 12 = 48 base 10

- 3E base 13 = 50 base 10 (E stands for Eleven)

- 3T base 14 = 52 base 10 (T stands for Ten)

- 39 base 15 = 54 base 10

- 30 base 24 = 72 base 10

- 2(23) base 25 = 73 base 10 (the ``units digit'' is 23)

- 2(22) base 26 = 74 base 10

- 20 base 48 base 10 = 96 base 10

- 1(47) base 49 = 96 base 10

- 1(48) base 50 = 98 base 10

- 1(47) base 51 = 98 base 10

- 11 base 97 = 98 base 10

- 10 base 98 = 98 base 10

- 0(97) base 99 = 97 base 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!

FWIW, the Goodstein function grows much more rapidly than Ackermann's function.

ReplyDelete