Open Problem Garden - Termination of the sixth Goodstein Sequence - Comments

The actual value is much higher (re: Termination of the sixth Goodstein Sequence)

Deedlit — Fri, 17 Sep 2010 16:42:37 +0200

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.)

approximate value (re: Termination of the sixth Goodstein Sequence)

Deedlit — Fri, 17 Sep 2010 16:33:50 +0200

So how much is in terms of, say, Knuth arrows? we have

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.

Nah, I just posted it here (re: Termination of the sixth Goodstein Sequence)

kagidab — Sat, 21 Aug 2010 10:37:27 +0200

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.

Has this solution been (re: Termination of the sixth Goodstein Sequence)

Anonymous — Tue, 17 Aug 2010 22:23:35 +0200

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

Solution (re: Termination of the sixth Goodstein Sequence)

kagidab — Fri, 04 Jun 2010 03:43:55 +0200

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 :

Termination of the sixth Goodstein Sequence

mdevos — Tue, 07 Oct 2008 15:54:26 +0200

Author(s): Graham

Subject: Logic

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