Re: Growth Rate of Level-k Goodstein Function

"Deedlit" <roycepeng@xxxxxxxxxxx> wrote ...

r.e.s. wrote:

The version using F_a seems to be another way of writing what I
posted 2006-09-21 (my x_i are your c_i, and my p is your m) ...

g_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a - a

that is,
B_2(n) = f_p^x_p f_(p-1)^x_(p-1) ... f_0^x_0 a

where many parentheses are omitted for easier reading, and where

f_0 (t) = t + 1
f_(k+1) (t) = f_k^(t+1) (t).


Hmm... I think for this to work, there has to be an increment on the
limit ordinals as well. I've seen the GW hierarchy with t+1 as the
exponent, but not in the fundamental sequence.

No limit ordinals are used in the above recursion for g_2, just
nonnegative integers -- the extended hierarchy isn't needed here.
(Your recursion for g_2 in terms of the F_a also doesn't involve
limit ordinals, although the Hardy hierarchy version does.)

BTW, I think it can be shown by induction that above f_k and F_k,
for nonnegative integer k, are simply related by

F_k (n+1) = f_k (n) + 1

so that both recursions for g_2 (in the F_k and in the f_k) are
equivalent. I also see now that your recursion for g_2 in terms
of the Hardy hierarchy follows from that of the F_k because of
the general relationships

F_a (n) = H_(w^a) (n)
H_(a+b) (n) = H_a(H_b(n))
H_(w^(a+1)) (n) = (H_(w^a))^n (n)

Hence all three recursions for g_2 (in the f_k, F_k, and H_a)
are equivalent.


A question about terminology ...

I see the F_a hierarchy variously called the Wainer hierarchy,
the extended Grzegorczyk hierarchy, and the Grzegorczyk-Wainer
hierarchy; but, as I recall, the f_a (appropriately defined at
limit ordinals) were used by Wainer in his 1989 JSL paper
"Slow Growing versus Fast Growing". Are the f_a sometimes also
called "the Wainer hierarchy"?

I'd say they would also be called by any of the above names, just like
there are numerous variants of the Ackermann function.

That's what I figured, since I think that when the f_a are
appropriately defined at limit ordinals, F_a(n+1) = f_a(n) + 1,
so that for an arbitrary function h, (h ~ F_a) <=> (h ~ f_a).
(By h ~ F_a, I mean a is the least ordinal such that as n ->oo,
h(n)/F_(a+1)(n) -> 0, etc.) That is, both hierarchies effect
the same calibration of growth rates.
.

Relevant Pages

  • Re: [ckrm-tech] [RFC][PATCH 6/8] RSS controller shares allocation
    ... Won't it eat all the stack in case of a deep tree? ... The depth of the hierarchy can be controlled. ... Recursion is needed ... for any infrastructure that supports a hierarchy. ...
    (Linux-Kernel)
  • Re: Expanding Hierarchies - SQL 2000
    ... no recursion is a plus ... Get a copy TREES & HIERARCHY IN SQL and look at the Nested Sets model ...
    (comp.databases.ms-sqlserver)
  • Re: copy a folder and its contents
    ... This comes as no surprise because you are trying to copy a folder ... hierarchy into a folder which is inside that hierarchy. ... the recursion is in your copying. ...
    (comp.lang.ruby)
  • Re: Growth Rate of Level-k Goodstein Function
    ... where H is the Hardy hierarchy, ... H_a = H_) for a limit, and athe fundamental sequence ... I see the F_a hierarchy variously called the Wainer hierarchy, ... the extended Grzegorczyk hierarchy, and the Grzegorczyk-Wainer ...
    (comp.theory)
  • Re: Growth Rate of Level-k Goodstein Function
    ... No limit ordinals are used in the above recursion for g_2, ... nonnegative integers -- the extended hierarchy isn't needed here. ... that perhaps we could use the Hardy hierarchy and index them by ...
    (comp.theory)