Simple set
In computability theory a simple set is an example of a set which is recursively enumerable but not recursive.
Definition
A subset S of the natural numbers N is called simple if it satisfies the following properties
- N\S is infinite
- S is recursively enumerable
- S ∩ X ≠ ø for any infinite recursively enumerable set X
 | This computer science article is a stub. You can help Wikipedia by expanding it. |