## Quick Reference

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.

**From:**
recursive set
in
A Dictionary of Computing »

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.