recursively enumerable

For a language $L$, TFAE:

• There exists a Turing machine $f$ such that $\forall x.(x\in L)\iff \text{the computation }f(x)\text{ terminates}$.

• There exists a total recursive function $f:\mathbb{N}\to L$ which is onto.

• There exists a total recursive function $f:\mathbb{N}\to L$ which is one-to-one and onto.

A language $L$ fulfilling any (and therefore all) of the above conditions is called recursively enumerable.

Examples

1. Any recursive language.

2. The set of encodings of Turing machines which halt when given no input.

3. The set of encodings of theorems of Peano arithmetic.

4. The set of integers $n$ for which the hailstone sequence starting at $n$ reaches 1. (We don’t know if this set is recursive, or even if it is $\mathrm{N}$; but a trivial program shows it is recursively enumerable.)