Primitive recursive functions are the "blue" functions in the book "Gödel, Esher, Bach". They corresponds to functions that can be computed by programs without loops (except for loops... but NO WHILE). It can be proven that Ackermann functions is not a primitive recursive function.

If you add while-loops, you have mu-recursive functions. It corresponds intuitively to computable functions. It concides with functions that can be computed by Turing machines. Ackermann is a mu-recursive functions.

i think μ-recursive functions are exactly equivalent to Turing machines; but not every every μ-recursive function is a primitive recursive function(though they are related); Ackermann(your example) function is a good example; please have a look at

http://en.wikipedia.org/wiki/%CE%9C-recursive_function

 Hassan Abedi :

Thanks!

According to you (as many books say)

μ-recursive function = primitive recursive function+minimal function

But  Ackermann function seems to belong neither primitive recursive function nor minimal function ; That is  Ackermann function is not μ-recursive function , then it should not be computed! in fact it can be computed! You do not answer if  Ackermann function belongs to μ-recursive function or not.

@ Stefan Gruner   ：

I am high appreciated for your help! But I can't communicate via http://www.researchgate.net you show.

If convinient , I hope see your note about the proof of Ackemann fucntion belonging to Mu-recursion.

@Peter T Breuer :

Thanks for your helpful answer!

The problems lies in that:

if  mu-recursive = primitive recursive + minimun recursive

Ackeman function belongs to neither primitive recursive nor  minimun recursive

Then how does Ackeman function belong to mu-recursive function?

@Stefan Gruner ：

Thank you so much!!!

@ Stefan Gruner ·

Dear  Stefan Gruner ·

In fact, I can't read it for it is a Germany text.

@ Peter T Breuer:

Could you tell me by which scheme Ackemann Function got? By primitive or Mu-operator scheme, or by other scheme? Thanks!

@Peter T Breuer   

Do you think that Ackemann function uses  mu-operator,so it can be expressed as g(x,y)=mimimal z in  f（x,y）=  z? There are three expressions of Ackemann function ,which one can be expressed as g(x,y)=mimimal z in f（x,y）=  z? 

@Peter T Breuer

You describe a process about how to compute Ackemann function. It is known now. Yet could you please directly answer by which scheme(s) to construct Ackemann function?

Thanks!!! 

I would like to ask how to construct Ackemann Function. If you get Ackemann function by primitive recursion or/and Mu-operator, and then you say Ackemann Function is not primitive recursive, is it OK?

You say Mu-recursive function is constructed by primitive recursion or Mu-operator, then, by which one among primitive recursion and Mu-operator does Ackeman function is constructed?

Information of China@ Peter T Breuer

OK！！！ I see! Now I understood your meaning and why Ackemann function is constructed by primitive recursion (and ... ) but not primitive recursive!

You are right and talent! Thank you very much and thanks other answers!

But I still have a question that there three equations in  Ackemann function , which one and why does it uses Mu-operator? Could you please write down an equation in  Ackemann function in the form of Mu-operator express (like g(x,y)=minimal z in f(x,y)=z)?

(i)   A(0,y)=y+1

(ii)  A(x+1,0)=A(x,1)

(Iii)  A(x+1,y+1)=A(x,A(x+1,y))

A(1,1)=A(0,A(1,0))      (iii)

          =A(0,A(0,1))      (ii)

          =A(0,2)              (i)

           =3

Do you mean:

"μc:∀p

@Peter T Breuer

Is

∀p

@ Peter T Breuer

Do you refer the second form

to Ack(M,N)=μw:∀p

Because (i)   A(0,y)=y+1

then, A(0,0)=0+1=1

Could I say 1 is the  μw ?

You say " selecting the least function in a certain domain that satisfies a certain condition."

By "the least function", do you mean the Ackemann function (including three sub-equations) producing a least projection (smallest value of the function) among many circles of computation of the equation when m,n taking values many times?

@ Peter T Breuer

Oh! You paid so much time for my question which might be common sense for you!  Thank you so much!

I care why Ackemann function is of Mu-operator in form.

As to answer if allow to break, I think,when a double-variable input is given , the loop should not interupting until completing (at this step, we say it is breaking.) So breaking should be allowed only in case completing all the loops nested in the most outer loop.

According to you ,now ,I understand so:

For well-order inputs ,say ,,,......,the least  input  will get Mu w;

For a given input ,say , if we allow to interrupt loops ( I mean, to analyze into internal programs, and get a local result) ),then, the final loop will be whose result is Mu w for any nested loops including the outer loop.

Is this understanding right?

OK! Thanks again !!!

Let's make this simple--every computable, and even partially computable, function is mu-recursive. Ackermann is computable and thus mu-recursive.

The point of the Ackermann function is that there is no direct proof that it is mu-recursive, you basically need to use the general proof that computable functions are mu-recursive, which you can find in many recursion/computability theory textbooks.

Primitive recursive functions are the "blue" functions in the book "Gödel, Esher, Bach". They corresponds to functions that can be computed by programs without loops (except for loops... but NO WHILE). It can be proven that Ackermann functions is not a primitive recursive function.

If you add while-loops, you have mu-recursive functions. It corresponds intuitively to computable functions. It concides with functions that can be computed by Turing machines. Ackermann is a mu-recursive functions.

@ Breuer,Gruner,Schwarzentruber, Fortnow 

Thank you for your answers above!

I have understood your words and accepted your proposiions that  Ackermann function really belongs to Mu-recursive function.There is a little dificult that  Ackermann  function is made up by primitive recursion (although and Mu-operator) yet not  primitive recursion. It is is true yet with some dificulty to be understood! Now the difficult is overcome by your helps!!!