Recursively Enumerable Language

Definition

A formal language $L$ is recursively enumerable (or Turing-recognizable) if there exists a Turing machine $M$ such that:

1. If $w\in L$, $M$ halts and accepts $w$.
2. If $w\notin L$, $M$ either halts and rejects $w$ or loops forever.

Enumerator

Equivalently, $L$ is RE if there exists a deterministic Turing machine (an enumerator) that lists all strings in $L$ (possibly with repetition) on an output tape.

Relation to Decidability

If a language $L$ and its complement $\bar{L}$ are both RE, then $L$ is decidable.