Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Each given hyperoperation can be implemented by a bounded loop of the previous hyperoperation. – ex0du5 May 11 '13 at 6:45
straight answer welcomed!!! (so, if I got it right, any of them can be computed using a do-loop?) – Wolphram jonny May 11 '13 at 6:59
up vote 4 down vote accepted

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.

share|cite|improve this answer
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. – r.e.s. Oct 18 '15 at 7:02
Of course @r.e.s. , this remark link us to the Ackermann-like functions topic. – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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