Talk:Slow-growing hierarchy

Origin

Does anyone know who originally proposed the slow-growing hierarchy? I learned of it from (Gallier 1991) and it doesn't cite any source. Cheers, — sligocki (talk) 23:02, 7 December 2009 (UTC)

Schwichtenberg's "Classifying Recursive Functions" (1997) says, in reference to the ε₀-recursive functions ...

"Girard[1981] has shown that one might as well associate a far bigger ordinal with the functions provably recursive in arithmetic, the Bachmann-Howard ordinal.

To this end, Girard has introduced the so-called slow growing hierarchy G_α, α < the Bachmann-Howard ordinal ..."

I suppose, however, that that doesn't eliminate the possibility of some earlier-defined version of the hierarchy up to an ordinal smaller than the B-H ord. (BTW, I'm accessing this via Google preview of pp. 541-542 of "Handbook of computability theory", 1999, E. R. Griffor, ed.)

— r.e.s. 16:48, 16 December 2009 (UTC)

something is wrong?

If g0(n)=0, then g1(n)=g0(n)+1=0+1=1; g2=g1(n)+1=1+1=2 and so on.

I think something is wrong written in article, because it has no sense to insert counting sequence in this article —Preceding unsigned comment added by 83.21.60.126 (talk) 17:59, 27 April 2011 (UTC)

No, that's the correct result — so you can see why this hierarchy is called "slow growing". In fact, if α is represented in Cantor normal form, then g_α(n) is the result of replacing ω by n everywhere in the Cantor normal form. Thus the functions with integer index i are just constants (g_i(n) = i for all n), and the first non-constant function in this hierarchy occurs when the index is ω (g_ω(n) = n). Similarly, g_{ω·i + j}(n) = n·i + j, and so on.
— r.e.s. (talk) 02:54, 28 April 2011 (UTC)

The actual entries for the counting sequence are f₀(-1) = 0, f₀(0) = 1, f₀(1) = 2 and so on, as f₀(n) = n + 1.

Catching ordinal

I'm pretty sure that the slow-growing hierarchy catches up the fast-growing one at large Veblen ordinal. 31.42.233.14 (talk) 11:39, 21 April 2013 (UTC)

The slow-growing hierarchy catches up the fast-growing one at $\theta (\Omega _{\omega })$, as it can be seen here.

$f_{0}(n)=g_{\omega +1}(n)$

$f_{1}(n)=g_{\omega 2}(n)$

$f_{2}(n)=g_{2^{\omega }\omega }(n)$

$f_{\omega +1}(n)=g_{\Gamma _{0}}(n)$

$f_{\omega 2+1}(n)=g_{\theta (\Omega 2)}(n)$

$f_{\omega ^{2}+1}(n)=g_{\theta (\Omega ^{2})}(n)$

$f_{\omega ^{\omega }+1}(n)=g_{\theta (\Omega ^{\Omega })}(n)$

$f_{\omega ^{\omega ^{\omega }}+1}(n)=g_{\theta (\Omega ^{\Omega ^{\Omega }})}(n)$

$f_{\omega ^{\omega ^{\omega ^{\omega }}}+1}(n)=g_{\theta (\Omega ^{\Omega ^{\Omega ^{\Omega }}})}(n)$

$f_{\epsilon _{0}+1}(n)=g_{\theta (\Omega \uparrow \uparrow \omega )}(n)$

$f_{\theta (\Omega )}(n)=g_{\theta (\Omega _{2})}(n)$

$f_{\theta (\Omega _{2})}(n)=g_{\theta (\Omega _{3})}(n)$

$f_{\theta (\Omega _{3})}(n)=g_{\theta (\Omega _{4})}(n)$

When the fast-growing hierarchy reached Ω, the slow-growing hierarchy reached Ω₂ and therefore, the slow-growing hierarchy index adds only 1 to the first Ω-subscript of the fast-growing hierarchy index.

$f_{\theta (\Omega _{m})}(n)=g_{\theta (\Omega _{m+1})}(n)$

However, its significance becomes less and less as this subscript grows bigger.

$f_{\theta (\Omega _{10})}(n)=g_{\theta (\Omega _{11})}(n)$

$f_{\theta (\Omega _{100})}(n)=g_{\theta (\Omega _{101})}(n)$

$f_{\theta (\Omega _{1000})}(n)=g_{\theta (\Omega _{1001})}(n)$

$f_{\theta (\Omega _{10000})}(n)=g_{\theta (\Omega _{10001})}(n)$

So, it is safe to say, that $f_{\theta (\Omega _{\omega })}(n)=g_{\theta (\Omega _{\omega })}(n)$, as ω ≫ 1 and therefore, ω + 1 is basically the same as ω.

So, the slow-growing hierarchy and the fast-growing hierarchy will meet together at Ω_ω. Therefore, when the fast-growing hierarchy reaches Ω_Ω, the slow-growing hierarchy will also have Ω_Ω, as Ω ≫ ω ≫ 1.

$f_{\theta (\Omega _{\Omega })}(n)=g_{\theta (\Omega _{\Omega })}(n)$ — Preceding unsigned comment added by 84.151.248.103 (talk) 13:03, 13 September 2020 (UTC)

exception

The slow-growing hierarchy and the fast-growing hierarchy will meet together at Ω_ω. But, there is an exception.

The exception is additions.

If there are additions, the slow-growing hierarchy and the fast-growing hierarchy will meet together, if the first ordinal is Ω and has more than 1 subscript.

$f_{\theta (\Omega _{\omega +1})}(n)=g_{\theta (\Omega _{\omega +2})}(n)$

$f_{\theta (\Omega _{\epsilon _{m+1}})}(n)=g_{\theta (\Omega _{\epsilon _{m+1}})}(n)$

$f_{\theta (\Omega _{\Omega +1})}(n)=g_{\theta (\Omega _{\Omega +2})}(n)$

$f_{\theta (\Omega _{\Omega _{\Omega +1}})}(n)=g_{\theta (\Omega _{\Omega _{\Omega +1}})}(n)$

Inconsistent?

Maybe I'm reading it wrong, but the first paragraph and the end of the second paragraph of the section "Relation to the fast-growing hierarchy" seem to contradict each other. The first paragraph seems to assert (regardless of what choice of fundamental sequences is made) that f_ε0 is only matched by the growth of g at the Bachmann-Howard ordinal. The end of the second paragraph seems to assert that for a certain choice of fundamental sequences, they match (at the same ordinal) as early as $\omega ^{2}$. Does the first statement implicitly use one of the standard definitions of fundamental sequences? And what is the (counterintuitive?) choice of fundamental sequences that would make them match up at $\omega ^{2}$? Or am I missing something? I don't have easy access to the references, or I'd look it up. Spireguy (talk) 04:24, 3 April 2017 (UTC)

Slow-growing hierarchy, but the greek letters are replaced by well-known large numbers.

g_ω^ω2(4) = 65536

How large are g_{Graham's number}(4), g_TREE(3)(4), g_SSCG(3)(4), g_SCG(13)(4), g_{Loader's number}(4), g_{Rayo's number}(4) and g_{Fish number 7}(4)? — Preceding unsigned comment added by 84.154.66.177 (talk) 07:55, 9 June 2020 (UTC)

g_{Graham's number}(4) ≈ 2²⁶²¹⁴⁴ ≈ 1.61×10⁷⁸⁹¹³