recursive set
recursive set A subset A of a set B is said to be recursive, relative to B, if there is an algorithm or effective procedure that, given an element b in B, will output “yes” if b is an element of A and “no” if b is not an element of A. The set A is thus also said to be decidable or computable.
Strictly speaking the sets A and B should be sets of natural numbers, and the algorithm is a definition of the total recursive function that is the characteristic function of A in B. The concept and terminology is transferred to other data sets using a Gödel numbering.
Post's theorem says that a set A is recursive iff A and B–A are recursively enumerable.
Strictly speaking the sets A and B should be sets of natural numbers, and the algorithm is a definition of the total recursive function that is the characteristic function of A in B. The concept and terminology is transferred to other data sets using a Gödel numbering.
Post's theorem says that a set A is recursive iff A and B–A are recursively enumerable.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
recursive set