The Goodstein sequence G(m) of a number m is a sequence of natural numbers. The first element in the sequence G(m) is m itself. To get the second, G(m)(2), write m in hereditary base-2 notation, change all the 2s to 3s, and then subtract 1 from the result. In general, the (n + 1)-st term, G(m)(n + 1), of the Goodstein sequence of m is as follows:


Early Goodstein sequences terminate quickly. For example, G(3) terminates at the 6th step:


Later Goodstein sequences increase for a very large number of steps. For example, G(4) OEIS: A056193 starts as follows:


Elements of G(4) continue to increase for a while, but at base ${\displaystyle 3\cdot 2^{402\,653\,209}}$, they reach the maximum of ${\displaystyle 3\cdot 2^{402\,653\,210}-1}$, stay there for the next ${\displaystyle 3\cdot 2^{402\,653\,209}}$ steps, and then begin their descent.


However, even G(4) doesn't give a good idea of just how quickly the elements of a Goodstein sequence can increase. G(19) increases much more rapidly and starts as follows:


In spite of this rapid growth, Goodstein's theorem states that every Goodstein sequence eventually terminates at 0, no matter what the starting value is.

The Goodstein function, ${\displaystyle {\mathcal {G}}:\mathbb {N} \to \mathbb {N} }$, is defined such that ${\displaystyle {\mathcal {G}}(n)}$ is the length of the Goodstein sequence that starts with n. (This is a total function since every Goodstein sequence terminates.) The extremely high growth rate of ${\displaystyle {\mathcal {G}}}$ can be calibrated by relating it to various standard ordinal-indexed hierarchies of functions, such as the functions ${\displaystyle H_{\alpha }}$ in the Hardy hierarchy, and the functions ${\displaystyle f_{\alpha }}$ in the fast-growing hierarchy of Löb and Wainer:


Some examples:


(For Ackermann function and Graham's number bounds see fast-growing hierarchy#Functions in fast-growing hierarchies.)

Application to computable functions[edit]

Goodstein's theorem can be used to construct a total computable function that Peano arithmetic cannot prove to be total. The Goodstein sequence of a number can be effectively enumerated by a Turing machine; thus the function which maps n to the number of steps required for the Goodstein sequence of n to terminate is computable by a particular Turing machine. This machine merely enumerates the Goodstein sequence of n and, when the sequence reaches 0, returns the length of the sequence. Because every Goodstein sequence eventually terminates, this function is total. But because Peano arithmetic does not prove that every Goodstein sequence terminates, Peano arithmetic does not prove that this Turing machine computes a total function.