I apologize if this question is too basic. I have read that the Ackerman function is the first example of a computable but NOT primitive recursive function. Hyperoperators seem to be closely related to these functions, but I am not sure if they still keep the property of being NOT primitive recursive. My intuition is that they are, but I am not sure. Any textbook or references to read to get a better understanding of this will be very appreciated (and a straight response too!).

NOTE: I read this related question, but it doesnt help me.

  • $\begingroup$ Each given hyperoperation can be implemented by a bounded loop of the previous hyperoperation. $\endgroup$ – ex0du5 May 11 '13 at 6:45
  • 1
    $\begingroup$ straight answer welcomed!!! (so, if I got it right, any of them can be computed using a do-loop?) $\endgroup$ – Wolphram jonny May 11 '13 at 6:59

If I have understood well yes.

Because if follow from the definiton of hyperoperators definition.


is the successor function, and every hyperoperation is defined recursively from the successor function:

(recursive definition of $H_{n+1}$ using $H_n$)

$i)$ $H_{n+1}(a,0):=a_{n+1}$

$ii)$ $H_{n+1}(a,b+1):=H_n(a,H_{n+1}(a,b))$

Here $a_{n+1}$ is the initial value of the function when the argument is $0$ and in the case of hyporoperators we have that

$a_ {n+1}:= \begin{cases} a, & \text{if $n=0$} \\ 0, & \text{if $n=1$ } \\ 1, & \text{if $n\gt 1$ } \\ \end{cases}$

Since $H_0(a,b)=S(b)$ is the successor funtion and is basic primitive rucursive funtion, we have that all the hyperoperations (that are defined from $H_0(a,b)=S(b)$) are Primitve recursive functions.

  • 3
    $\begingroup$ It's worth mentioning that although each hyperoperation $H_n:\mathbb{N}^2 \to \mathbb{N}$ is primitive recursive, the function $H: \mathbb{N}^3 \to \mathbb{N}: (n,x,y) \mapsto H_n(x,y)$ is not primitive recursive. A simple proof of this is skecthed in Introduction to Computability Theory by Zucker & Pretorius. $\endgroup$ – r.e.s. Oct 18 '15 at 7:02
  • $\begingroup$ Of course @r.e.s. , this remark link us to the Ackermann-like functions topic. $\endgroup$ – MphLee Oct 18 '15 at 8:49

(Elaborating on my comment to the accepted answer ...)

For each $n \in \mathbb{N}$, the $n$th hyperoperation $$H_n: \mathbb{N}^2 \to \mathbb{N}: (x,y) \mapsto H_n(x,y)$$ is primitive recursive.

However, for any integer constant $c\ge 2$, the following functions are not primitive recursive:

$$\begin{align} f_c&: \mathbb{N} \to \mathbb{N}: n \mapsto H_n(c,n)\\ g_c&: \mathbb{N}^2 \to \mathbb{N}: (n,y) \mapsto H_n(c,y)\\ h&: \mathbb{N}^3 \to \mathbb{N}: (n,x,y) \mapsto H_n(x,y). \end{align}$$

When $n$ is included as an argument, the function grows too fast to be primitive recursive.

E.g., $x\uparrow^n y\ $ is primitive recursive as a function of $(x,y)$ for fixed $n$, but it is not primitive recursive as a function of $(n,y)$ for fixed $x\ge 2$.

Essentially these results are proved in Chapter 13 of "Computability, Complexity, and Languages" (1983) by Davis & Weyuker, and also sketched in Introduction to Computability Theory by Zucker & Pretorius.


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.