recursively enumerable set

A Dictionary of Computing | 2004 | 643 words | Copyright

recursively enumerable set A subset A of a set B is said to be recursively enumerable, relative to B, if there is an effective procedure that, given an element b in B, will output “yes” if and only if b is an element of A. If b is not in A then, in general, the procedure will never terminate. This is a weaker notion than that of a recursive set. A set can be recursively enumerable without being recursive. The set A is also said to be semidecidable or semicomputable.

The set of Ada programs that terminates (for a given input) is recursively enumerable (with respect to the class of all Ada programs) but it is not recursive.

Cite this article
Pick a style below, and copy the text for your bibliography.

MLA
Chicago
APA

JOHN DAINTITH. "recursively enumerable set." A Dictionary of Computing. 2004. Encyclopedia.com. 27 May. 2012 <http://www.encyclopedia.com>.

JOHN DAINTITH. "recursively enumerable set." A Dictionary of Computing. 2004. Encyclopedia.com. (May 27, 2012). http://www.encyclopedia.com/doc/1O11-recursivelyenumerableset.html

JOHN DAINTITH. "recursively enumerable set." A Dictionary of Computing. 2004. Retrieved May 27, 2012 from Encyclopedia.com: http://www.encyclopedia.com/doc/1O11-recursivelyenumerableset.html

Learn more about citation styles