partial recursive function

views updated

partial recursive function A function on the natural numbers that can be obtained from certain initial functions by a finite number of applications of composition, primitive recursion, and minimization. In general the function may not be defined for certain values of its argument and so is a partial function. The initial functions used are normally the zero function, successor function, and projection functions. The partial recursive functions can be defined in many ways and, according to the Church–Turing thesis, are precisely the functions on natural numbers that can be defined by algorithms. See also primitive recursive function.