The primitive one must be constructed by zero, successor, projection, composition and primitive recursion function.
The idea of primitive recursion function is : for a list of variables that can be induction, induct on them one by one, not jumping to next one before the current one reach the base case.
primitive recursion function is only a subset of (general) recursive function(or computable one), some function like Ackman is (general) recursive, but not primitive one.
Here give an excellent proof if this.
2008年10月21日星期二
订阅:
博文评论 (Atom)
没有评论:
发表评论