Intereting Posts

Generating a $\sigma$-algebra from a $\sigma$-ring
Elementary proof of Zsigmondy's theorem
Two-Point boundary value problem
If $G$ is a group and $N$ is a nontrivial normal subgroup, can $G/N \cong G$?
Calculate skewness and kurtosis fast
Every ordered field has a subfield isomorphic to $\mathbb Q$?
Prove that every positive integer $n$ is a unique product of a square and a squarefree number
If an $H\le G$ has an irreducible representation of dimension $d$, then show $G$ has an irreducible representation of at least dimension $d$.
Complex Functions: Integrability
Why are projective morphisms closed?
Why is the expected number coin tosses to get $HTH$ is $10$?
Are $L^\infty$ bounded functions closed in $L^2$?
Different ways to prove there are infinitely many primes?
Is $\Bbb Q(\sqrt 2, e)$ a simple extension of $\Bbb Q$?
Alternate ways to prove that $4$ divides $5^n-1$

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.

- How to extend this extension of tetration?
- Are points on the complex plane sufficient to solve every solvable equation composed of the hyperoperators, their inverses, and complex numbers?
- Could someone tell me how large this number is?
- Algorithm for tetration to work with floating point numbers
- Example $x$, $y$ and $z$ values for $x\uparrow^\alpha y=z$ where $\alpha\in \Bbb R-\Bbb N$
- Notation for n-ary exponentiation

- How many combinations can I make?
- $ T(n)= T(\log n)+ \mathcal O(1) $ Recurrence Relation
- How to derive a closed form of a simple recursion?
- Can't find the demonstration of a theorem about recursion
- Explicit solution of the recursion $x_n = x_{n-1}^2 - 2$ with $x_0>2$
- Is there a name for the recursive incenter of the contact triangle?
- Proving a recurrence relation for strings of characters containing an even number of $a$'s
- Proving convergence of a sequence
- The problem of the most visited point.
- Find recursive formula for sequence $a_n = \left(\frac23\right)^n + n$

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.

- Longest sequence of minimally finer topologies
- $2\times2$ matrices are not big enough
- Understanding the Equation of a Möbius Strip
- Group actions transitive on certain subsets
- How to average cyclic quantities?
- prove that $\tan(\alpha+\beta) = 2ac/(a^2-c^2)$
- Quadratic subfield of cyclotomic field
- Proving $ \frac{x^3y^2}{x^4+y^4}$ is continuous.
- How eigenvalues and eigenvectors of this matrix are obtained?
- Partial derivatives in circular permutation
- Summing Finitely Many Terms of Harmonic Series: $\sum_{k=a}^{b} \frac{1}{k}$
- Solve problem of trigonometry.
- Why the number of ways of selecting $r$ things out of $n$ identical things is 1
- Closed form for $\int_0^{\infty}\sin(x^n)\mathbb{d}x$
- Prove that $6|2n^3+3n^2+n$