Termination of the sixth Goodstein Sequence

Importance: Low ✭
Author(s): Graham, Ronald L.
Subject: Logic
Keywords: Goodstein Sequence
Recomm. for undergrads: no
Prize: $25 Graham
Posted by: mdevos
on: October 7th, 2008

\begin{question} How many steps does it take the sixth Goodstein sequence to terminate? \end{question}

For a positive integer $n$, the $n^{th}$ \Def{Goodstein Sequence} is defined as follows. The first term of the sequence in $n$. To obtain the $k^{th}$ term, write the $(k-1)^{st}$ term in \Def[hereditary base k notation]{Goodstein Sequence}, change all $k$'s to $(k+1)$'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:

\[ \begin{array}{lll} \mbox{term} & \mbox{value} \\ 1 & 2^2 + 2 = 6\\ 2 & 3^3 + 2 = 29\\ 3 & 4^4 + 1 = 257 \\ 4 & 5^5 = 3125 \\ 5 & 5 \cdot 6^5 + 5 \cdot 6^5 + 5 \cdot 6^4 + 5 \cdot 6^3 + 5 \cdot 6^2 + 5 \cdot 6 + 5 = 46655 \end{array} \]

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

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.

approximate value

So how much is $F_6(6) - 2$ in terms of, say, Knuth arrows? we have $$ F_6(6) = F_5^6(6) = F_5^5(F_5(6)) = F_5^5(F_4^6(6)) = ... = F_5^5(F_4^5(F_3^5(F_2^6(6))))

F_2(6) = 2^6*6 = 384

F_2^2(6) = 2^384 * 384 > 2^{392}

F_2^6(6) > 2^{2^{2^{2^{2^{392}}}}}

F_5^5(F_4^5(F_3^5(F_2^6(6)))) > (2\uparrow\uparrow\uparrow\uparrow)^5 (2\uparrow\uparrow\uparrow)^5 (2\uparrow\uparrow)^5 (2^{2^{2^{2^{2^{392}}}}}) $$ 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 $\omega$. Call the result R(n). The value of G(n) is then $$H_{R(n)}(3) - 2$$ where $H_a(x)$ is the Hardy hierarchy, defined by

$H_0(x) = x$

$H_{a+1} (x) = H_a (x+1)$

$H_a (x) = H_{a[x]} (x) $ for limit ordinals a

So to find G(6), we write $6 = 2^2 + 2$, so $R(6) = \omega^\omega + \omega$. Hence, $$ G(6) = H_{\omega^\omega + \omega} (3) - 2 = H_{\omega^\omega}( H_{\omega} (3)) - 2 = F_{\omega} (F_1 (3)) - 2 = F_{\omega} (6) - 2 = F_6 (6) - 2 $$

where $F_a(x)$ is the fast-growing hierarchy, defined by

$F_0(x) = x+1$

$F_{a+1} (x) = F_a^x (x)$

$F_a (x) = F_{a[x]} (x)$ 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

$k(a,n)=$ amount of steps to reduce $(a-1)*a^n+(a-1)a^{n-1}+...(a-1)a^0$ to -1

$(a-1)a^1+a-1\rightarrow(a-1)(a+a)^1-1\rightarrow(a-2)(2a)^1-(2a-1)$

If you do this a - 1 times: $(a - 1) a ^ 1 + a - 1 -> a * 2^{a - 1} - 1$

Which means it is reduced to a 0th power and will take $a*2^{a-1}$ steps to finish.

So total steps $=a(2^{0}+2^{1}+2^{2}+...+2^{a-2})+a*2^{a-1}=a*(2^{a}-1)=k(a, 1)+1$

For $(a-1)*a^n+(a-1)a^(n-1)+... +(a-1) a^0$:

$k(a,n) = k(k...k(a,n-1)...)) - 2 $ [k a times]

$f(n)=g(h(n)-2,h(n), h(n))-2$

Where $g(o) = g(0, n, o) = o * 2^o$, $g(m, n, o)=g(m - 1, n, g(g(...g(o)))...)$ [n copies of g] and $h(n)$ is the first number in the sequence in the form $(a - 1) * a^(a-1)+(a - 1) a ^ (a - 2) + ... (a - 1)$ $h([3,4,5,6,7])=[2, 3, 4, 6, 8]$

E.g.

$f(4) = g(1, 3, 3) - 2 = g(0, 3, g(g(g(3)))) - 2 = 3 * 2^{402653211} - 2$

Using $g(n)\sim2^{n}$:

$f(6) = g(4,6,6)-2\sim g(3, 6, 2\uparrow\uparrow 7})\sim2\uparrow\uparrow25$

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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.