In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
The class of all recursively enumerable languages is called RE.
Post's theorem shows that RE, together with its complement co-RE, correspond to the first level of the arithmetical hierarchy.
Indeed, one can run the Turing machine and accept if the machine halts, hence it is recursively enumerable.
That is, if L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well: Recursively enumerable languages are not closed under set difference or complementation.