Talk:Fast-growing hierarchy

Tip: Anchors are case-sensitive in most browsers.

This article links to one or more target anchors that no longer exist.

[[Ackermann function#Ackermann numbers|Ackermann number]] The anchor (#Ackermann numbers) is no longer available because it was deleted by a user before.

Please help fix the broken anchors. You can remove this template after fixing the problems. | Reporting errors

f_ε₀(n)[edit]

Am I understanding this correctly as being: f_n↑↑n(n)? — Preceding unsigned comment added by 216.163.254.2 (talk) 12:28, 24 June 2011 (UTC)[reply]

No, that's not correct. In the Wainer hierarchy, f_n↑↑n(n) ≤ f_ω+1(n) for all n > 0. (In fact, even f_n↑ⁿn(n) ≤ f_ω+1(n) for all n > 0, where n↑ⁿn is the nth Ackermann number.)

When the subscript is a limit ordinal α (so α-1 does not exist), f_α(n) is defined to be f_α[n](n), where α[n] is the nth term of the specified fundamental sequence for α. As defined in the article, the fundamental sequence for ε₀ is ε₀[n] = ω↑↑(n-1) for n > 0; however, some authors (e.g. [Prӧmel, et al., 1991]) do take take ε₀[n] = ω↑↑n instead. (Here ω↑↑n denotes ω↑(...ω↑(ω↑(ω))...) with n omegas.) For n > 1 in either case, ε₀[n] is not a finite ordinal like n↑↑n or n↑ⁿn, but is an exponential tower of ωs (still a limit ordinal), which must then be replaced by the nth term of its fundamental sequence, etc. etc., until eventually obtaining a successor ordinal (which might still be infinite!). When the subscript is a successor ordinal, say β, the next step is to replace f_β(n) by the n-fold iteration f_β-1(...f_β-1(f_β-1(n))...), then to continue by applying the appropriate reduction to f_β-1(n), etc. etc. For any n > 1, this process applied to f_ε₀(n) eventually produces a finite formula that contains no infinite ordinals at all, but the formula is much more complex than f_n↑↑n(n) or f_n↑ⁿn(n).

Here's an example showing a few steps, using the more-convenient alternative definition ε₀[n] = ω↑↑n:

f_ε₀(2)

= f_ω^ω(2) because (ε₀)[2] = ω^ω

= f_ω²(2) because (ω^ω)[2] = ω²

= f_ω·2(2) because (ω²)[2] = ω·2

= f_ω+2(2) because (ω·2)[2] = ω+2

= f_ω+1(f_ω+1(2)) because (ω+2)-1 = ω+1

= f_ω+1(f_ω(f_ω(2))) because (ω+1)-1 = ω

= f_ω+1(f_ω(f₂(2))) because (ω)[2] = 2

= f_ω+1(f_f₂(2)(f₂(2))) because (ω)[f₂(2)] = f₂(2)

= f_ω(...f_ω(f_ω(f_ω(f_f₂(2)(f₂(2)))))) with f_f₂(2)(f₂(2)) "f_ω"s, because (ω+1)-1 = ω

= f_ω(...f_ω(f_ω(f_{f_f₂(2)(f₂(2))}(f_f₂(2)(f₂(2)))))) with f_f₂(2)(f₂(2)) - 1 "f_ω"s, because ω[f_f₂(2)(f₂(2))] = f_f₂(2)(f₂(2))

= f_ω(...f_ω(f_{f_{f_f₂(2)(f₂(2))}(f_f₂(2)(f₂(2)))}(f_{f_f₂(2)(f₂(2))}(f_f₂(2)(f₂(2)))))) with f_f₂(2)(f₂(2)) - 2 "f_ω"s, because ω[f_{f_f₂(2)(f₂(2))}(f_f₂(2)(f₂(2)))] = f_{f_f₂(2)(f₂(2))}(f_f₂(2)(f₂(2)))

= ... with one fewer "f_ω" at each step, until none of the f_f₂(2)(f₂(2)) "f_ω"s remain ...

= f_X(X) where X is a very lengthy finite formula containing no ωs.

Note that f_2↑↑2(2) is far less than even the number of "f_ω"s involved in the evaluation of f_ε₀(2).

(Contrast this "complexity" of f_ε₀(n) with that of f_ω(n), for which a finite formula free of infinite ordinals is immediately given by f_ω[n](n) = f_n(n).)
— r.e.s. (talk) 20:09, 26 June 2011 (UTC)[reply]

I understand now. Thank you. Just to make sure I understand one small sub-point:

f_ω²(2) = f₈⁸(8), right? Not f₂(8)?

In other words, if you have f_ω²(2), you can't just convert the ω to n. You have to treat it as f_ω(f_ω(2)), the first ω becoming n, and the second ω becoming f₂(2), right?

This is how I interpreted things based on your kind extrapolation of ε₀ into a finite ordinal, but I wanted to be sure. — Preceding unsigned comment added by 216.163.254.2 (talk) 16:56, 22 July 2011 (UTC)[reply]

Almost, but not quite. It should be f_ω²(2) = f_ω(f_ω(2)) = f_ω(f₂(2)) = f_ω(8) = f₈(8)
— r.e.s. (talk) 18:05, 22 July 2011 (UTC)[reply]

Ahh not sure why I put an ⁸ there. But that's what I meant. Thanks.

f_ε₀(2) is much larger than Graham's number since: f_ω+1(64) = f_ω⁶⁴(64) > f_ω⁶⁴(6) > G and f_ε₀(2) = f_ω+1(f₈(8)) — Preceding unsigned comment added by 216.163.255.2 (talk) 15:52, 29 August 2011 (UTC)[reply]

f_ω+1(f₈(8)) is special. Same result we get for f_ω+2(2), f_2ω(2), f_η₀(2) and more. :) See [Allam's numbers page] Liso (talk) 12:36, 19 March 2020 (UTC)[reply]

Is this function total computable? I think so, because we can use transfinite induction to prove that fε0(n) can be converted to form without epsilon number. Similiary we can prove than fεx(n) can be converted to form with at most fε(x-1)(n) (I think) 83.21.59.98 (talk) 18:49, 16 April 2012 (UTC)[reply]

f_ω(n)?[edit]

I'm having a hard time understanding what is meant by this function. How is f_ω(n) not infinite?

The article states f_ω(n) = A(n, n)

To me it seems like something infinite is somehow supposed to be equal to something finite.

What am I missing here? — Preceding unsigned comment added by 216.163.254.2 (talk) 18:20, 14 June 2011 (UTC)[reply]

Actually, the article says

f_ω(n) = f_n(n) > 2 ↑^{n - 1} n > 2 ↑^{n − 2} (n + 3) − 3 = A(n, n) for n ≥ 2

i.e., it's an inequality relation: f_ω(n) > A(n, n) for n ≥ 2.

Possibly you're confused by the mere appearance of the symbol ω in the name of this function (f_ω).

if f_ω(n) = f_n(n) then why the use of omega? see here: http://en.wikipedia.org/wiki/Large_numbers#Systematically_creating_ever_faster_increasing_sequences this article explicitly states that the symbol ω is meant to refer to the infinite ordinal. so to me it still seems as though f_ω(n) should refer to an infinite function. and if that article was indeed using ω to refer to n, should I assume that this article is using ε₀ to refer to n↑↑n? why not just say that? and what's so special about tetration? why not n↑↑↑n or n→n→n→...(n →'s)...→n?

For any nonnegative integer n, f_ω(n) means exactly f_n(n), which is always a nonnegative integer (not infinite).
— r.e.s. (talk) 17:33, 15 June 2011 (UTC)[reply]

then ω in this context is not the infinite ordinal i'm used to. because f_a(n) increases as a increases. it doesn't limit off as a increases. therefore if a = ω, then f_ω(n) is at least ω. the wainer hierarchy converts infinite ordinals to finite things. — Preceding unsigned comment added by 216.163.255.2 (talk) 11:52, 22 June 2011 (UTC)[reply]

Would just like to say (now that I understand this stuff perfectly), that my question could have been answered, and understanding could have been bestowed by anyone willing to simply point out that the hierarchy in question is a diagonalization process. And to mention that for infinite ordinals, we evaluate the ordinal as the nth element of the ordinal's set. Or the nth element of a set of which the ordinal is the supremum.

I know most of this is implied by the article, but it makes no mention of diagonalization whatsoever. — Preceding unsigned comment added by 216.163.246.2 (talk) 11:44, 26 July 2011 (UTC)[reply]

fundamental sequence rule[edit]

if λ = α + β, with β < α, then λ[n] = α + β[n],

I still don't think that this is right. what if α = ω³ + ω and β = ω²?

I think this should be something like if β is the smallest power of ω in the Cantor normal form of λ. What do you guys think? Cheers, — sligocki (talk) 05:37, 4 November 2009 (UTC)[reply]

You're right. I think it would be enough to just say at the beginning, "For λ < ε₀, written in Cantor normal form:" (according to Gallier, p.61.) Thanks for catching these points.

r.e.s. (talk) 13:10, 4 November 2009 (UTC)[reply]

If α = ω³ + ω and β = ω², then α + β = ω³ + ω², because ω + ω² = ω². In other words, the ordering, "ω followed by a copy of ω²" has order type ω². Addition is associative, but not commutative, with order-types. — Preceding unsigned comment added by 76.102.84.197 (talk) 21:08, 14 December 2012 (UTC)[reply]

And, to belabor the point, we get λ[n] = ω³ + ωn, but α + β[n] = ω³ + ω(n+1). Ben Standeven (talk) 17:59, 2 February 2013 (UTC)[reply]

Löb–Wainer hierarchy?[edit]

Is this the same as the Löb–Wainer hierarchy referred to by Rose (1984)? Originally from Löb–Wainer (1970-71), Hierarchies of number theoretic functions? Rose uses a different definition, but this looks like what he's referring to. Cheers, — sligocki (talk) 18:46, 4 November 2009 (UTC)[reply]

Except for using n instead of n + 1 iterations, this is the same hierarchy that Rose attributes to "Tait, Lob, Wainer, et al". A 1991 paper by Proemel, Thumser, and Voigt, "Fast growing functions based on Ramsey theorems", p. 345, (available online) calls this the "Wainer hierarchy", and says it is actually a modification due to Ketonen & Solovay in 1981. I haven't seen the latter paper, but I suspect that's where the modified number of iterations might have originated. — r.e.s. (talk) 15:38, 5 November 2009 (UTC)[reply]

Omega[edit]

Why is omega used for the set of natural numbers, instead of N? —Anonymous Dissident^Talk 02:47, 7 November 2009 (UTC)[reply]

N (unlike ω) is ambiguous about whether 0 is an element. Of course this could be stated explicitly. -- r.e.s. (talk) 14:41, 7 November 2009 (UTC)[reply]

It also seemed a little weird to me to use omega, so I switched it and wrote explicitly the numbers. Cheers, — sligocki (talk) 18:47, 7 November 2009 (UTC)[reply]

Hardy hierarchy and slow-growing hierarchy[edit]

Motivated by WP:Make stubs, I started articles for both Hardy hierarchy and slow-growing hierarchy based on the very limited information I have. Please edit/expand/fix as needed. Cheers, — sligocki (talk) 07:39, 1 December 2009 (UTC)[reply]

Copy of article[edit]

~~Does anyone have a copy of the original (Löb and Wainer 1970) paper? I'd appreciate any help in getting a hold of a copy. Cheers, — sligocki (talk) 23:52, 7 December 2009 (UTC)~~[reply]

Never mind, got it. Cheers, — sligocki (talk) 20:07, 9 December 2009 (UTC)[reply]

Are all f computable?[edit]

I'm concerned about this statement:

Every f_α is a total computable function.

Specifically, I believe that it depends upon the fundamental sequences being computable. For example, I could define the fundamental sequence for ω to be ω[n] = Σ(n) (the busy beaver function). But even for less perverse systems it's unclear. For example, let's choose only computable functions for fundamental sequences up to the Church-Kleene ordinal, ω^CK. Then we could define a fundamental sequence for ω^CK by ω^CK[n] = the largest ordinal represented by one of the first n enumerated computable functions. This fundamental sequence is clearly not computable and I don't think there's any reason to believe that f^{ω^{CK would be computable. Cheers, — sligocki (talk) 01:06, 9 December 2009 (UTC)}}[reply]

The fundamental sequences for limit ordinals not greater than ε₀ (all of which are computable) are specified in the article, so this question pertains to their definition for limit ordinals larger than ε₀. I think we can safely say that computability is tacitly assumed, if not explicitly stated, for any fundamental sequence assigned to a recursive limit ordinal. I don't have a source that mentions extending the fast-growing hierarchy beyond the recursive ordinals, so I'm not sure the question concerning the Church-Kleene ordinal actually pertains to this hierarchy.
— r.e.s. 17:34, 9 December 2009 (UTC)[reply]

I completely agree that this statement is true for the defined levels of the hierarchy up to ε₀. However, the section says:

Following are some relevant points of interest about the fast-growing hierarchy {f_α| α < μ}:

with μ unconstrained. The hierarchy can be defined up to any ordinals we can define fundamental sequences for. And, as I've stated, there is a way to define a fundamental sequence for the Church-Kleene ordinal even though no such sequence is computable. I think that the statement just needs to be reworded. We could be conservative and say: for all α < ε₀ given the above fundamental sequences. Or we could be a little more liberal and allow all α < μ for arbitrary μ, but require that all the fundamental sequences be computable.

As a personal aside, this came up because I have been considering the extension of the fast-growing hierarchy to the Church-Kleene ordinal and I am curious if I could show anything about f_ω^CK. For example, is it uncomputable? Cheers, — sligocki (talk) 19:42, 9 December 2009 (UTC)[reply]

My comment was concerning "the" fast-growing hierarchy, which I take to be some particular one that presumably appears in published sources (as per WP subject matter). It seems extremely likely that any published source that actually specifies a particular fast-growing hierarchy will have chosen the fundamental sequences to be computable, even though this is not a requirement. E.g., as in Buchholz & Wainer [1987](p. 180), in a section titled "The Fast Growing Hierarchy" (italics are mine):

By 'a fast growing' hierarchy we simply mean a transfinitely extended version of the Grzegorczyk hierarchy i.e. a transfinite sequence of number theoretic functions F_α defined recursively at successor levels and diagonalisation over suitable fixed fundamental sequences at limit levels. [...] We are concerned with the ordinals below ε₀ [...] The version of The Fast Growing Hierarchy we shall choose is the following [...]

I think an improved opening paragraph to the present article would be along similar lines:

In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy) is an ordinal-indexed family of rapidly increasing functions f_α: N → N (where N is the set of natural numbers {0, 1, ...}, and α ranges up to some large countable ordinal). A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < ε₀. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity.

Various adjustments would then be needed in other sections for consistency with this usage of "a" as opposed to "the" hierarchy.
— r.e.s. 15:04, 14 December 2009 (UTC)[reply]

Ah, yes. Thank you very much r.e.s.! This has been above and beyond clarified. Cheers, — sligocki (talk) 21:45, 14 December 2009 (UTC)[reply]

Does f_ε₀ dominate the Goodstein function?[edit]

The present section "Functions in the hierarchy" states that

f_ε₀(n) is the first function in the hierarchy which dominates the Goodstein function (based on the fundamental sequence chosen in this article).

However, the fundamental sequences in the article are those used by Gallier[1991], according to whom (in his Theorem 12.6) the Goodstein function—let's call it G here— dominates H_ε₀ in the Hardy hierarchy. Doesn't it then follow that G dominates f_ε₀? (Other authors simply state that G has "approximately" the same growth-rate as f_ε₀, dominating every f_α for which α < ε₀.) In any case, I'm unaware of a proof that f_ε₀ dominates G -- is there a source for this?
— r.e.s. 14:58, 9 December 2009 (UTC)[reply]

--

It's original research on my part, here's my reasoning:

H_{\epsilon _{0}}(n)=H_{\omega \uparrow \uparrow n}(n)

given our fundamental sequences (using a natural extension of Knuth up-arrow notation to the ordinals)

Likewise, by Cichon's characterization of the Goodstein function (Cichon 1983, see Goodstein function#References)

{\mathcal {G}}((2\uparrow \uparrow n)-1)=H_{\omega \uparrow \uparrow n}(1)-1

So,

H_{\epsilon _{0}}(n)>{\mathcal {G}}((2\uparrow \uparrow n)-1)>{\mathcal {G}}(n)

QED

As for the contradiction with Gallier, I don't know what to say. Gallier does not prove that Goodstein majorizes H_epsilon, he only claims it is due to Kirby and Paris. But I see no mention of the Hardy hierarchy in Kirby and Paris... I haven't been able to get ahold of the Buchholz and Wainer paper which Gallier also cites. Cheers, — sligocki (talk) 20:07, 9 December 2009 (UTC)[reply]

Actually, I found another problem with Gallier recently. He claims that Girard proved that there is an ordinal such that slow-growing and fast-growing hierarchies meet and that ordinal is the Howard ordinal (Theorem 12.4). He says that Cichon and Wainer (1983) provide an alternative proof. They do not, they show that

g_{\alpha }

reaches

f_{\epsilon _{0}}

when α is the Howard ordinal. This is very different! I have tried to read Girard to find out the original statement, but his monogram is long, technical and difficult and I haven't been able to come up with anything. However, Cichon and Wainer actually prove their statement while Gallier only claims it. This leads me to wonder what else in Gallier is suspect. Cheers, — sligocki (talk) 20:28, 9 December 2009 (UTC)[reply]

--

Very nice — thanks for resolving this issue. Now that I know what to look for, I can see that your results are implicit in the paper by Caicedo ("Goodstein's function") cited at Goodstein's theorem#References, which restates some of Cichon's work and gives all the necessary relationships among the two different versions of the Goodstein function, the fast-growing hierarchy, and the Hardy hierarchy. As you've pointed out elsewhere, this H version of the Hardy hierarchy is not quite the same as the h version, due to using very slightly different fundamental sequences; but this makes no difference in the results, since both H_ε₀ and h_ε₀ (and hence f_ε₀) dominate both versions of the Goodstein function.
— r.e.s. 06:44, 10 December 2009 (UTC)[reply]

Relation with the Grzegorczyk Hierarchy[edit]

At level 1, the proposed function does not "coincide with [that] of the Grzegorczyk hierarchy": $\lambda x.2x$ vs. $\lambda x.x^{2}+2$ , the problem being that you cannot generate ${\mathcal {E}}^{2}$ from $\lambda x.2x$ . Löb and Wainer (1970) or Wainer (1972) have some specific definitions for the functions at level 0 or 1 in order to fix this, e.g. $F_{1}(x)=(x+1)^{2}$ in Wainer (1972).

Sylvain Schmitz (talk) 18:50, 18 May 2010 (UTC)[reply]

Part of the problem is that the term "Grzegorczyk hierarchy" is used in two distinct ways in the literature. Historically, it refers to the hierarchy of *sets* of functions described in the article on the Grzegorczyk hierarchy; however, more-recent literature also uses the same term in reference to the finite-index (α < ω) initial segment of the fast-growing hierarchy. I've edited the article in an attempt to clarify this, but still haven't found a convenient and clear terminology to distinguish these. ("Grzegorczyk hierarchy of indexed sets of functions" and "Grzegorczyk hierarchy of indexed functions" seems awkward.)
— r.e.s. (talk) 16:17, 19 May 2010 (UTC)[reply]

Relationship to the Hardy hierarchy[edit]

In the Points of Interest section, the article had stated

The Wainer hierarchy of functions f_α is related to the Hardy hierarchy of functions h_α by the relation f_α(n) = h_ω^α(n). Hence, f_ε₀ = h_ε₀. (Gallier 1991)

I've corrected this to reflect that the equality relation holds only for α < ε₀, and that although f_ε₀ ≠ h_ε₀, nevertheless there is the result stated in Gallier:
At α = ε₀, the Hardy hierarchy "catches up" to the Wainer hierarchy, in the sense that f_ε₀(n-1) ≤ h_ε₀(n) ≤ f_ε₀(n+1).
— r.e.s. (talk) 15:24, 4 June 2010 (UTC)[reply]

References[edit]

First link in the Gallier reference does not work.Jzimba (talk) 20:47, 6 January 2015 (UTC)[reply]

Bird's array notation[edit]

Ever since the article on Bird's array notation was deleted, the entries in "Approximate_growth_rates_in_comparison_to_other_googological_notations" have been completely without context. As such, almost the entire section will need to be rewritten in some notation that is actually notable, in order to make any sense. –LaundryPizza03 (d c̄) 06:06, 19 July 2019 (UTC)[reply]

For reference, the googological notations with articles on Wikipedia are Knuth's up-arrow notation (which can denote values on the order of f_omega without requiring ellipses), Steinhaus-Moser notation (2 in an n-gon is comparable to f_omega(n)), Cutler's bar notation (less powerful than up-arrows), Conway chained arrow notation (Conway's cg(n) is comparable to f_(omega^2)(n)) and Bowers's operators (more powerful than chained arrows if the array has 5 or more elements). Graham's number is comparable to f_(omega+1)(64). Only Conway's and Bowers's notations would appear after f_(omega+1). Arcorann (talk) 02:50, 18 November 2019 (UTC)[reply]

In the Bowers's operators article, it says that "Numbers like TREE(3) are unattainable with Bowers's operators", and in the TREE(3) article, it says that "It can be shown that the growth-rate of the function TREE is at least

f_{\theta (\Omega ^{\omega }\omega )}

in the fast-growing hierarchy"; this implies that Bowers's notations are insufficient to represent every growth rate function in the fast-growing hierarchy. 173.230.18.196 (talk) 23:59, 3 December 2019 (UTC)[reply]

At the time of writing, the Bower's Operators page has also been deleted. At present, Bashicu Matrix System, Bird's Array Notation, Bowers's operators all point to non-existent pages, and it is not easy to find any reference for what these notations are via general google searching. Perhaps it is sensible to append descriptions of these notations to the bottom of this section.Chalisque (talk) 16:19, 9 May 2020 (UTC)[reply]

'Such to'[edit]

'Let μ be a large countable ordinal such to every limit ordinal'...

'Such to' is a very unusual formation in english. Did you mean 'such that'? Comiscuous (talk) 23:34, 8 April 2021 (UTC)[reply]

fε0(n)[edit]

fω(n)?[edit]