How fast can the base-bumping function in Goodstein's theorem grow? In the usual presentation of Goodstein's theorem, the base is bumped up by the "add 1" function. Does the theorem still hold when we replace this function by a fast-growing one (e.g. Ackermann or busy beaver)? How far can we push this? For example, let's define $g_0(n)$ to be the number of Goodstein iterations needed to reach 0 when we start with base 2 and seed $n$ (so that $g_0(0)$ = 0). Then we can build a hierarchy of functions by defining $g_{k+1}(n)$ as the number of Goodstein iterations needed to reach 0 with seed $n$ and base-bumping function $g_k$ ($k$ = 0, 1, ...), continuing through the ordinals by diagonalization at each limit ordinal. Surely it's got to break down when we go past $\varepsilon_0$, if not long before that! 
 A: Dear all,
let me give the following remark:
"Goodstein actually employed arbitrary increasing base-bumping functions. He showed that the convergence of all such is equivalent to transfinite induction below ϵ0."
This statement has to be taken with care when it comes to weakly increasing base bumping
functions. When we reach functions in the neighboorhood of log* then the Goodsteinprocess
becomes provable in PRA. 
But when we take a fixed iterate of log then of course termination of Goodstein
sequences is equivalent to the 1 consistency
of PA.
If the base bumping function growth faster than H_epsilon_0 then Goodstein
can of course yield more than the 1 consistency of PA.
Best,
Andreas
A: Goodstein actually employed arbitrary increasing base-bumping functions. He showed that the convergence of all such is equivalent to transfinite induction below $\epsilon_0$. This is illustrated somewhat more graphically by the Hercules vs. Hydra game. See the references from my old post [1] of 1995 which helped serve to popularize these topics on (use)net. Curiously that post received far more feedback than any of my other posts - from popular science writers to researchers, teachers and students.
[1] Bill Dubuque, sci.math, Dec 11, 1995. Goedel's theorem: about anything in real world?
http://groups.google.com/groups?selm=WGD.95Dec11023450@martigny.ai.mit.edu
A: As long as your fast-growing "base-bumping" function still takes every natural number to a natural number (instead of, say, an infinite ordinal)--and the busy beavers do--the Goodstein iterations are still upper-bounded by the strictly-decreasing sequence of ordinals in "base" $\omega$, which must be of finite length as a decreasing sequence in a well-ordered set.
A: First, let me say that this is a really great question. 
It seems to me that any increasing base-bumping function would give the
same Goodstein result that you eventually hit $0$. That is, I claim that for any increasing
sequence of bases $b_1$, $b_2$ and so on, if we define the
Goodstein sequence by starting with any number $a_1$, and
then if $a_n$ is defined, we write it in complete base
$b_n$, replace all instances of $b_n$ with $b_{n+1}$,
subtract $1$, and call the answer $a_{n+1}$. The theorem
would be that at some point $n$ in the construction, we
have $a_n=0$.
The proof of the original theorem proceeded by associating
any number $a$ in complete base $b$ with the countable
ordinal obtained by replacing all instances of $b$ with the
ordinal $\omega$ and interpreting the resulting expression
in ordinal arithmetic. They key fact is that the ordinal
associated with $a$ in base $b$ is strictly larger than the
ordinal associated in base $b+1$ with the number obtained
by replacing all $b$'s with $b+1$'s and subtracting $1$.
If we replace $b$ with some larger $b'$ and
do the same thing, then it appears that this key fact still goes
through, since it was proved by observing what happens when the subtract-$1$ part causes a complex term to be broken up with coefficients below the new base. Thus, the newly associated ordinals would still 
be descending, so they must hit $0$, but this happens only
if the numbers themselves hit $0$.
