It is (I believe) a very easy exercise to prove that the general recursive functions over the natural number object $N$ form a category. But what sort of category is it? From the fact that one can prove the Recursion Theorem one might surmise that the category of general recusive functions over $N$ is cartesian closed, but what other category-theoretic properties does it have?

Question 1: Is it possible (for example) to characterize the category of general recursive functions over $N$ without having to deem specific functions as 'recursive' (as Kleene does in his papers)?

Furthermore, we now have types of 'recursiveness' over various structures, i.e. $\alpha$-recursive functions, $\beta$-recursive functions ($\alpha$-,$\beta$-recurision over the ordinals); Koepke and Koerwien's $\ast$-recursive functions over the ordinals (which characterize the constructible universe $L$), and Infinite Time Turing Machines; Sacks' $E$-recursion; Recursive functionals and quantifiers of finite type (Kleene); primitive recursive set functions and rudimentary set functions (Jensen, and others for studying the fine structure of $L$); abstract first-order computability (Moschovakis), to name but a few.

Question 2: Can (or has) category theory (been able to) elucidate the structural interrelations between the various types of recursion?

Since I am certain that there is a subfield of category theory devoted to answering these types of questions (and probably already have answered some of these questions), I would be interested in obtaining a list of survey articles devoted to this subdiscipline, and (of course) the answers to the two questions I asked (the second can be answered from the survey articles by giving a few concrete examples).

Thanks in advance for any and all help given.

6more comments