Recursive Set

A set  of integers is said to be recursive if there is a total recursive function  such that  for  and  for . Any recursive set is also recursively enumerable.

Finite sets, sets with finite complements, the odd numbers, and the prime numbers are all examples of recursive sets. The union and intersection of two recursive sets are themselves recursive, as is the complement of a recursive set.

REFERENCES

Davis, M. Computability and Unsolvability. New York: Dover 1982.

Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.