# recursively enumerable set

**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.

#### More From encyclopedia.com

Set Theory , A set is a collection of things. A set can consist of real or literal numbers (such as 1, 2, 3, 4 or a, b, c, d) or of objects (such as baseballs or… Boolean Algebra , Boolean algebra is often referred to as the algebra of logic, because the English mathematician George Boole, who is largely responsible for its begi… Set (seth) , set1 / set/ • v. (set·ting ; past set ) 1. [tr.] put, lay, or stand (something) in a specified place or position: Dana set the mug of tea down | Cath… Reset , re·set / rēˈset/ • v. (-set·ting ; past and past part. -set ) [tr.] set again or differently: I must reset the alarm. ∎ Electr. cause (a binary devic… Inset , in·set • n. / ˈinˌset/ a thing that is put in or inserted: a pair of doors with their original stained-glass insets. ∎ a small picture or map inserte… Venn Diagram , Venn diagram A schematic representation of a set, first used in the 19th century by John Venn. A universal set U will typically be represented by a r…

#### You Might Also Like

#### NEARBY TERMS

**recursively enumerable set**