Thread: Primitive Recursive vs Recursive Functions

Please could someone explain to me the difference between a primitive recursive function and a recursive function. I don't really need a formal definition, I would like to understand the difference between them so I can learn more about Ackermann's functions.

All I know so far is that all PR functions are recursive, I don't really understand do-loops or while-loops which are used in some definitions of recursion that I've found.

Is a recursive function or a primitive recursive function a function which can be implemented with a Turing machine? Also what is a partially recursive function?

Many thanks

Steph

Hi, Treblesteph

The difference bettwen this two classes(a primitive recursive function and a recursive function) isusing operation of operation minimization to obtain recursive functions.

Def(recursive functions) :
--operations: superposition, Primitive recursion, minimization
--functions: 0-function, S(s)-'next' function, N[n, m] - 'selec' function

Def(primitive recursive function) :
--operations: superposition, Primitive recursion
--functions: 0-function, S(s)-'next' function, N[n, m] - 'selec' function


Ackermann's function is an example of computable not a primitive recursive function

Sorry but I still don't understand - I can't follow the notation you've used. Could you (or someone else) please explain it more simply?