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 onetoone 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.
Title  recursively enumerable 

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