# recursively enumerable

For a language $L$, TFAE:

• There exists a Turing machine $f$ such that $\forall x.(x\in L)\iff\mbox{the computation f(x) 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. 1.
2. 2.

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

3. 3.

The set of encodings of theorems of Peano arithmetic.

4. 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 $\mathbb{N}$; but a trivial program shows it is recursively enumerable.)

Title recursively enumerable RecursivelyEnumerable 2013-03-22 12:44:32 2013-03-22 12:44:32 ariels (338) ariels (338) 6 ariels (338) Definition msc 03D25 semi-recursive HaltingProblem TuringComputable semi-recursive recursively enumerable function