on termination

[Jon Fairbairn]

On 2003-05-12 at 21:53+0300 Eray Ozkural wrote:

> I've seen many constructions on primitive recursive
> functions but what I don' t understand, not having the
> required expertise on recursive function theory, is
> whether the set of primitive recursive functions
> correspond to recursive sets in theory of computation.

They don't, because

> [...] Ackermann's function was a recursive function that
> was not primitive.

If I remember correctly, that's the chief reason Ackermann
came up with the function. Have a look at <URL:
http://mathworld.wolfram.com/AckermannFunction.html > and
the links on that page for computable and primitive
recursive, and see if that helps. The site also has a
definition of recursive.


 Jón

-- 
Jón Fairbairn                                 Jon.Fairbairn@cl.cam.ac.uk
31 Chalmers Road                                         jf@cl.cam.ac.uk
Cambridge CB1 3SZ            +44 1223 570179 (after 14:00 only, please!)