recursively enumerable set

'recursively enumerable set' can also refer to...


More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

Quick Reference

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.

Subjects: Computing.

Reference entries

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