A Dictionary of Philosophy, Third Edition
. Said of a procedure which can be applied to a starting point to get a certain result, and then re-applied to that result to get a further result, and so on. Adding one is a recursive procedure for generating the natural numbers from zero. Recursion theory is a branch of mathematical logic studying FUNCTIONS definable by such procedures. See also DEFINITION, INDUCTION.
A set is recursively enumerable if there is a procedure for generating its members (not necessarily in any given order).
If both a set and its complement (i.e. the set containing just those items in the relevant domain that are not members of the original set) are recursively enumerable then the set itself is called recursive. In that case there is a DECISION PROCEDURE for whether candidates for membership are or are not members: since there is a process for generating both members and non-members, we wait to see in which list the candidate item appears. With a merely recursively enumerable procedure we can prove that something is a member, if it is, but cannot prove it is not a member, if it is not. The predicate calculus, for instance (i.e. the set of its theorems), is recursively enumerable but not recursive.
This is the complete article, containing 205 words
(approx. 1 page at 300 words per page).
View More Summaries on Recursive
