Computably Enumerable

A set is called computably enumerable if its Pseudo-Characteristic Function is Computable.

Proposition

Let be nonempty. Then is computably enumerable if and only if there is a Computable function such that .

Proposition

Any Type 0 Formal Language is computably enumerable. (the converse also holds)

Proposition

The computably enumerable Formal Languages are closed under union, intersection, and concatenation; but not under complementation and difference.