# Termination of the sixth Goodstein Sequence

 Importance: Low ✭
 Author(s): Graham, Ronald L.
 Subject: Logic
 Keywords: Goodstein Sequence
 Prize: \$25 Graham
 Posted by: mdevos on: October 7th, 2008
Question   How many steps does it take the sixth Goodstein sequence to terminate?

For a positive integer , the Goodstein Sequence is defined as follows. The first term of the sequence in . To obtain the term, write the term in hereditary base k notation, change all 's to 's and then subtract 1. If the sequence hits 0, then it terminates. So, the first terms of the sixth Goodstein Sequence are as follows:

Surprisingly, despite the fact that Goodstein Sequences grow quite quickly at the start, all such sequences do eventually hit 0 and terminate. This result, first discovered by Goodstein, is of interest in logic since it cannot be proved in Peano arithmetic.

Although determining particular properties of a specific Goodstein Sequence are of limited mathematical value, this problem is an interesting computational challenge.

## Bibliography

* indicates original appearance(s) of problem.

### approximate value

So how much is in terms of, say, Knuth arrows? we have That's about as close an approximation as you can get.

### The actual value is much higher

You've underestimated the true value by quite bit.

To get the value of the Goodstein function at n, you take n, write it in hereditary base 2, then replace every appearance to with the infinite ordinal . Call the result R(n). The value of G(n) is then where is the Hardy hierarchy, defined by

for limit ordinals a

So to find G(6), we write , so . Hence,

where is the fast-growing hierarchy, defined by

for limit ordinals a

(or you could just leave the answer in terms of the Hardy hierarchy, I just changed to the fast-growing hierarchy because the answer is a little simpler.)

### Solution

amount of steps to reduce to -1

If you do this a - 1 times:

Which means it is reduced to a 0th power and will take steps to finish.

So total steps

For :

[k a times]

Where , [n copies of g] and is the first number in the sequence in the form

E.g.

Using :

### Has this solution been

Has this solution been verified by the author? Just curious.

### Nah, I just posted it here

Nah, I just posted it here as my attempt at a solution. It probably needs to be done a bit better, but I believe it works until n = 8 or so, where you have to do a bit extra. I might try make it a bit clearer and rigorous at some point. Plus a better approximation would be useful.