# Are hyperoperators primitive recursive?

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.

#### Solutions Collecting From Web of "Are hyperoperators primitive recursive?"

If I have understood well yes.

Because if follow from the definiton of hyperoperators definition.

$H_0(a,b):=S(b)$

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.

(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.