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