Take the 2-minute tour ×
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.

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|improve this question
    
Each given hyperoperation can be implemented by a bounded loop of the previous hyperoperation. –  ex0du5 May 11 '13 at 6:45
1  
straight answer welcomed!!! (so, if I got it right, any of them can be computed using a do-loop?) –  julian fernandez May 11 '13 at 6:59
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

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.