2008年10月21日星期二

primitive recursion and general recursion

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.

没有评论: