3
$\begingroup$

Let us consider the class $\cal F$ of functions that contains

  • all constant functions
  • all projections
  • the successor function
  • the Ackermann function

as basic functions, and that is closed under composition and primitive recursion.

(If we remove the line with the Ackermann function from this definition, then this is the standard definition of the class of primitive recursive functions.)

My question: What function class $\cal F$ do we get by adding the Ackermann function as basic function? Do we get all $\mu$-recursive functions, or do we get some strange sub-class?

$\endgroup$
4
$\begingroup$

A very nice question!

You just ventured into a large body of knowledge and research in computational theory around the concept of relative primitive recursiveness and hierarchy of total recursive functions such as fast growing hierarchy, which are full of interesting and mind-boggling facts.

What function class $\cal F$ do we get by adding the Ackermann function as basic function?

Well, that is one of its own kind.

Do we get all $\mu$-recursive functions?

No. What we get are far far from all $\mu$-recursive functions since all functions we get are still total recursive functions as primitive recursion preserves totality. Recall that $\mu$-recursive functions means partially recursive functions or, what is equivalent, all functions that can be computed by Turing machines.

You might ask, then, do we get all total recursive functions?

The answer is still no. What we get are far from all total recursive functions. For example, a "Ackermann modification of Ackermann function" is not included. Here is a version of that "doubly Ackermann" function.

Let us start from the usual two-argument Ackermann–Péter function. $$A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}$$ Let $f(n)=A(n,n)$ be the Ackermann–Péter function of a single-argument. Now let us define $$D(m, n) = \begin{cases} f(n) & \mbox{if } m = 0 \\ D(m-1,1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ D(m-1, D(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}$$

Then $D(m,n)$ is a doubly Ackermann function, which cannot be obtained from composition and primitive recursion of Ackermann functions and all primitive recursive functions. This is not surprising, since a single Ackermann modification accelerates the growth of a strictly increasing function faster than arbitrarily finitely many compositions and primitive recursions.

You may continue to ask, what if we add that doubly Ackermann function? Then we are missing the "triply Ackermann functions". If you keep asking, then you will be building a growing hierarchy by Ackermann modification. Even if you have asked $\omega$ times this way, where $\omega$ is the first infinite ordinal, the growth rate of any function thus obtained is still dwarfed by most of functions in the fast growing hierarchy.

or do we get some strange sub-class?

You may call it some strange sub-class as you like. However, as you might have expected, it is not unusual at all in the field of computation theory. Here is an excerpt from paper The Ackermann functions are not optimal, but by how much? by H. Simmons, slighted edited.

5.1 DEFINITION. For each set $\Theta$ of functions, let $PR(\Theta)$ be the clone of those functions that can be obtained from members of $\Theta$ by primitive recursion. $PR(\Theta)$ is also called a primitive recursive degree. The primitive recursive degrees measure the complexity of functions up to primitive recursive equivalence.

The "strange sub-class" of yours is just $PR(\alpha)$, where $\alpha$ is the set of primitive recursive functions and the particular versions of Ackermann function you have in mind. In that paper, "by taking a closer look at the construction of an Ackermann function we see that between any primitive recursive degree and its Ackermann modification there is a dense chain of primitive recursive degrees."

Hopefully, I have shown you a glimpse of the fascinating theory around recursiveness and growth of total recursive functions. You may want to read some of the following articles as well as raise more interesting questions like this one.

Mind blown: the fast growing hierarchy for laymen — aka enormous numbers
Ackermann function
Higher-Order Recursion, How to Make Ackermann, Knuth and Conway Look Like a Bunch of Primitives, Figuratively Speaking

$\endgroup$
  • $\begingroup$ Thanks a lot for all the pointers to the literature! $\endgroup$ – Gamow Nov 12 '18 at 15:31
0
$\begingroup$

The limitation of "primitive recursive" functions is that for all loops, the iteration count must be calculated before the loop starts iterating, and must be calculated within the limitations of primitive recursive functions. You can't run loops that run for arbitrary long (but finite) time.

The Ackermann function on the other hand grows faster than can be calculated using any primitive recursive function. With your addition, you still can't run loops that run for arbitrary long (but finite) time, but you can run loops whose iteration count has to be calculated before the loop starts iterating, where the calculation can involve use of the Ackermann function.

So many functions that require huge iteration counts, so huge that they cannot be calculated with primitive recursive functions but can be calculated involving the Ackermann function, can now be computed.

I have no idea how difficult it is to define an "Ackermann-squared" function that grows too fast to be calculated using this model.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.