Redirected from Partial recursive function
Other equivalent function classes are the λrecursive functions[?] and the functions that can be computed by Markov algorithms.
Take as axioms the axioms of the primitive recursive functions, but extend the definitions so as to allow for partial functions. Add one further operator, the least search or unbounded search operator, defined as follows:
The set of partial recursive functions is defined as the smallest set of partial functions of any arity from natural numbers to natural numbers which contains the zero, successor, and projection functions, and which is closed under composition, primitive recursion, and unbounded search.
The set of recursive functions is the subset of partial recursive functions which are total.
In the equivalence of models of computability[?] the parallel is drawn between Turing machines which do not terminate for certain inputs and an undefined result for that input in the corresponding partial recursive function. The unbounded search operator is not definable by the rules of primitive recursion as those do not provide a mechanism for "infinite loops" (undefined values).
It is interesting to note that if the application of the unbounded search operator in the definition above is limited strictly to regular functions (functions which are guaranteed to be total when the unbounded search operator is applied to them), the resulting set (historically called the general recursive functions) is the same as the set of recursive functions  in other words, the requirement for partial functions can be partially obviated.
Search Encyclopedia

Featured Article
