on termination

Eray Ozkural erayo@cs.bilkent.edu.tr
Tue, 13 May 2003 12:22:11 +0300

On Tuesday 13 May 2003 01:17, Jon Fairbairn wrote:
> 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.

OK. Then isn't there an answer to the original question? I couldn't find a 
machine model that satisfies Cagdas's operational requirements. Any thoughts? 
Maybe it's a very easy answer but I can't see it, and I can't say I know the 
proof of every theorem in Cindrella book.


Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C