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.)

Title	recursively enumerable
Canonical name	RecursivelyEnumerable
Date of creation	2013-03-22 12:44:32
Last modified on	2013-03-22 12:44:32
Owner	ariels (338)
Last modified by	ariels (338)
Numerical id	6
Author	ariels (338)
Entry type	Definition
Classification	msc 03D25
Synonym	semi-recursive
Related topic	HaltingProblem
Related topic	TuringComputable
Defines	semi-recursive
Defines	recursively enumerable function