General recursive function

A partial recursive function that is defined for all values of its arguments. The concept of a general recursive function can also be defined independently of the concept of a partial recursive function as follows. The class of all general recursive functions is the smallest class of functions containing all primitive recursive functions (cf. Primitive recursive function) and closed under composition of functions and the least-number operator, under the condition that the latter is only applied to a function when

However, the study of general recursive functions is usually carried out within the class of all partial recursive functions. This is related, in particular, to the fact that there is no number for which there exists a general recursive function that is universal for the class of all -place general recursive functions.

All general recursive functions are explicitly definable in formal arithmetic (cf. Arithmetic, formal) in the sense that for any such function an arithmetical formula can be constructed with the following property: For any natural numbers , if , then ; but if , then , where are the terms representing the numbers , and the symbol denotes derivability in the arithmetic calculus.

References

[1]	P.S. Novikov, "Elements of mathematical logic" , Oliver & Boyd and Addison-Wesley (1964) (Translated from Russian)
[2]	E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)

References

[a1]	S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[a2]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165