on termination

Eray Ozkural erayo@cs.bilkent.edu.tr
Mon, 12 May 2003 21:53:22 +0300

On Friday 09 May 2003 21:33, oleg@pobox.com wrote:
> I'd like to clarify the termination decision procedure. I believe it
> can take the body of a function in our language and tell if the
> function terminates for all inputs. This implies that we can decide on
> termination without evaluating the function on all inputs (whose set
> is countably infinite).

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.

I got confused when I read that Ackermann's function was a recursive function 
that was not primitive. Could you please explain this to me?

Excuse me if I'm being ignorant about this subject.


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