Talk:Slow-growing hierarchy

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]