recursive

A procedure that is applied once, and then applied to the result of that application, and so on. A recursive definition (definition by induction) defines the result of some operation for 0, and then the result for any number n + 1 in terms of the result for n; thus the operation becomes defined for all numbers (the notion may be extended to describe the same process on any well-ordered set). For example, if n' denotes the successor of n, then multiplication may be defined: a × 0 = 0; a × b' = (a × b) + a.

A function in mathematics is primitive recursive if it is definable by recursion and substitution from a number of basic functions. These are commonly the successor function, the zero function (the function whose value is zero for every argument), the projection functions (that extract the ith member of any ordered n-tuple), and constant functions (that return the same number as value for any arguments).

A function is general recursive (or recursive) if it can be defined by means of primitive recursive functions and the minimization or µ operator. This defines a resulting function, h, out of a given function f according to the schema: h(x ₁… x _n) = the least y for which f(x ₁… x _n, y ) = 0 and is undefined if there is no such y .

A set is recursively enumerable if there is a recursive function that enumerates its members, i.e. if they can be ordered as f(0), f (1), f (2)…where f is a general recursive function. If both a set and its complement can be ordered, then the set is general recursive, or recursive. The importance of the notion is that it corresponds with being decidable, or effectively computable. Suppose, for example, that the theorems of some system form a recursive set, then we can find whether a candidate formula is a theorem by enumerating both the theorems and the non-theorems; we can be sure that in a finite time the formula will turn up on one list or another, and this procedure decides the matter. According to Church's theorem the set of theorems of the predicate calculus cannot be represented as a recursive set, so by Church's thesis the calculus is undecidable.