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

Question How many steps does it take the sixth Goodstein sequence to terminate?

For a positive integer $n$ , the $n^{th}$ 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 hereditary base k notation, 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

* indicates original appearance(s) of problem.

add new comment

approximate value

On September 17th, 2010 Deedlit says:

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

On September 17th, 2010 Deedlit says:

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

On June 4th, 2010 kagidab says:

$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

On August 17th, 2010 Anonymous says:

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

Nah, I just posted it here

On August 21st, 2010 kagidab says:

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.

Open Problem Garden