[FOM] Recursive but not p.r. computable functions -- the simplest "natural" examples???

[Andreas Weiermann]

In 2003 there has been some discussion on recursive but not
prim rec computable functions.
Herb Enderton wrote on 12.03.2003 for example:

>That point is exactly why you're having trouble!  The "real" reason
>the primitive recursive functions can't exhaust the class of
>calculable functions is that we can diagonalize out so easily.

It is quite natural to take a closer look at diagonalization
here. Matters turned out to be more interesting than expected
at first sight.

Let g be a start function and h be a function for controlling
the diagonalization.
So A_0(x)=g(x) and
A_{k+1}(x)=A_k^{h(x)}(x) where the upper index denotes number of iterations.
Let A(x):=A_x(x).
If g is the successor function and h is the identity function
then A is Ackermannian. It's easy to see that A is not prim rec.

Surprisingly when g is the successor function and h is
the binary length function then A is not Ackermannian.
This has been shown by Eran Omri in his MSc thesis as
a corollary to his investigations on Ramsey theory.

Together with him I showed the following extensions.

Let g_0(x)=x+epsilon (epsilon>0), g_{m+1}(x):=2^{g_m(log(x))}
where log is binary length. Moreover let h_m(x)=log^{m+1}(x) 
the (m+1)-th iterated binary length. Let A be defined
with respect to g_m and h_m. Then A is not Ackermannian.

If h'_m(x)=\sqrt[d](\log^{m}(x)) where d is fixed
and A is defined
with respect to g_m and h'_m, then A is Ackermannian.

The threshold for A moving from non Ackermannian to
Ackermannian can be classified more precisely but
notations become slightly involved. It is possible
to let d depend on x, and Ackermannian growth is then
guaranteed by taking the inverse Ackermann function for d.

Natural extensions hold for transfinite Ackermann hierarchies.
(  Just put A_lambda(x)=A_{lambda[h(x)]}(x).  )
Each omega power allows for one more application of log
in the definition of the corresponding h. The transfinite
hierarchy up to epsilon_0 collapses for h(x)=log^\star(x) which
is the inverse of
the superexponential function. The transfinite
hierarchy up to epsilon_0 does not collapse for h(x)=log^d(x)
when d is fixed.

Best regards,
Andreas Weiermann