Talk:Slow-growing hierarchy
![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
Origin
[edit]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 ε0-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?
[edit]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 (gi(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 f0(-1) = 0, f0(0) = 1, f0(1) = 2 and so on, as f0(n) = n + 1.
Catching ordinal
[edit]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 , as it can be seen here.
- When the fast-growing hierarchy reached Ω, the slow-growing hierarchy reached Ω2 and therefore, the slow-growing hierarchy index adds only 1 to the first Ω-subscript of the fast-growing hierarchy index.
- However, its significance becomes less and less as this subscript grows bigger.
- So, it is safe to say, that , 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.
- — Preceding unsigned comment added by 84.151.248.103 (talk) 13:03, 13 September 2020 (UTC)
exception
[edit]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.
Inconsistent?
[edit]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 . 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 ? 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.
[edit]gωω2(4) = 65536
How large are gGraham's number(4), gTREE(3)(4), gSSCG(3)(4), gSCG(13)(4), gLoader's number(4), gRayo's number(4) and gFish number 7(4)? — Preceding unsigned comment added by 84.154.66.177 (talk) 07:55, 9 June 2020 (UTC)
gGraham's number(4) ≈ 2262144 ≈ 1.61×1078913