FANDOM


Here I'll present a upper bound on Hydra(4) using King's method.

Let n be the steps that are already done.

The () hydra inside root pair just adds a step, corresponding to f0(n).

The (()) inside root pair expands to n ()'s, corresponding to f1(n).

The following table makes more comparisons like that.

Hydra inside root pair FGH ordinal
() 0
(()) 1
(()()) 2
(()()...()()) (n pairs) n
((())) ω
((())()) ω+1
((())()()) ω+2
((())(())) ω2
((())(())()) ω2+1
((())(())()()) ω2+2
((())(())()()()()) ω2+4
((())(())(())) ω3

To make the right bound, we must add a number to get a correct bound.

Look for example to the evaluation of hydra(3).

(((())))

((()()))

((())(())(()))

This would result in an upper bound of f1(f1(f1(2))) = 16, which isn't correct, as hydra(3) = 37.

If we add 2 to every step we do, it will be right:

(((())))

((()()))

((())(())(()))

((())(())()()()()), there are four not two.

((())(())()()())

((())(())()())

((())(())())

((())(()))

((())(())()()()()()()()()()), adding 1 here would be fine, but adding two is somewhat more secure. We must make sure that it is an upper bound.

We have this modified fast-growing hierarchy:

\(f'_0(n) = n+1\)

\(f'_{\alpha+1}(n) = f'^{n+2}_{\alpha}(n+2)\)

\(f'_{\alpha}(n) = f'_{\alpha[n+2]}(n+2)\)

For ordinals \(\alpha≥1\), the inequality \(f_{\alpha}(n+2) < f'_{\alpha}(n) < f_{\alpha}(n+3)\) holds.

((((()))))

(((()())))

(((())(())(())))

(((())(())()()()()))

\(f_{\omega2+4}(5) < \text{Hydra}(4) < f'_{\omega2+4}(3) < f_{\omega2+4}(6)\)

We can make it even tighter:

(((())(())()()()())) expands to (((())(())()()())((())(())()()())((())(())()()())((())(())()()())((())(())()()())). 

\(f^5_{\omega2+3}(5) < \text{Hydra}(4) < f'^5_{\omega2+3}(4) < f^5_{\omega2+3}(7)\)

And tighter: \(f^4_{\omega2+3}(f^5_{\omega2+2}(5)) < \text{Hydra}(4) < f'^4_{\omega2+3}(f'^5_{\omega2+2}(5)) < f^4_{\omega2+3}(f^5_{\omega2+2}(8))\)

And tighter: \(f^4_{\omega2+3}(f^4_{\omega2+2}(f^5_{\omega2+1}(5))) < \text{Hydra}(4) < f'^4_{\omega2+3}(f'^4_{\omega2+2}(f'^5_{\omega2+1}(6))) < f^4_{\omega2+3}(f^4_{\omega2+2}(f^5_{\omega2+1}(9)))\)

Hydra(5)

(((((()))))) expands to ((((())(())()()()()))) in 3 steps.

((((())(())()()()()))) corresponds to the ordinal \(\omega^{\omega2+4}\)

\(f_{\omega^{\omega2+4}}(5) < \text{Hydra}(5) < f'_{\omega^{\omega2+4}}(3) < f_{\omega^{\omega2+4}}(6)\)

Of course we can make it even tighter, using the same method as above.

Hydra(n)

\(f_{\omega^{\omega^{\omega2+4}}}(5) < \text{Hydra}(6) < f'_{\omega^{\omega^{\omega2+4}}}(3) < f_{\omega^{\omega^{\omega2+4}}}(6)\)

\(f_{\omega^{\omega^{\omega^{\omega2+4}}}}(5) < \text{Hydra}(7) < f'_{\omega^{\omega^{\omega^{\omega2+4}}}}(3) < f_{\omega^{\omega^{\omega^{\omega2+4}}}}(6)\)

\(f_{\omega^{\omega^{\omega^{\omega^{\omega2+4}}}}}(5) < \text{Hydra}(8) < f'_{\omega^{\omega^{\omega^{\omega^{\omega2+4}}}}}(3) < f_{\omega^{\omega^{\omega^{\omega^{\omega2+4}}}}}(6)\)

A general bound should follow from this.

The easiest bound is \(f_{\varepsilon_0}(n-3) << \text{Hydra}(n) << f_{\varepsilon_0}(n-2)\), of course.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.