- Definition 1. Given string
*w*as input, the algorithm halts and outputs YES if and only if*w*belongs to the language*L*. If*w*does not belong to the language*L*, the algorithm either runs forever, or halts and outputs NO.

Another equivalent definition is that a language *L* is **recursively enumerable** if it is empty or if there is an algorithm which *enumerates* the members of the language in the following sense:

- Definition 2. The algorithm takes a positive integer, say
*n*as an argument, and produces as output a string in the language*L*. For every string*s*which is in*L*there must be an*n*so that the algorithm produces the string*s*.

The equivalence of these two definitions can be seen as follows:

**1 -> 2** Given an algorithm *A* according to the first definition for language *L* (assumed to be non-empty), the following algorithm will enumerate *L* according to the second definition: Let *E* be an algorithm which enumerates *all* strings, and so that every string appears infinitely often in the enumeration. We write *E(n)* to denote the string produced by algorithm *E* on input *n*. Pick a fixed string *t* in *L* (possible since *L* is non-empty). The following algorithm enumerates *L*:

- Given integer
*n*, run algorithm*A*on input*E(n)*for*n*steps. If the answer is YES, output the string*E(n)*. Otherwise, output string*t*.

**2 -> 1** Given an algorithm *A* according to the second definition for language *L*, the following algorithm will answer the question whether a given string *s* belongs to *L* in the sense of the first definition:

- For all numbers
*n*, starting with 1, and continuing in sequence, test whether the string produced by algorithm*A*on input*n*is equal to*s*. When the first such*n*is found, output YES. (Otherwise, continue the LOOP)

Some partially decidable languages have an algorithm that always halts and answers YES or NO correctly. Those languages are called decidable languages or *recursive languages*. Some problems are recursively enumerable but not recursive. One example is the halting problem, which is the problem:

- Given a program and input parameters, will that program eventually halt when run with those parameters?

Another example is:

- Given a polynomial (in several variables) with integer coefficients, is it possible to find integer values for the variables so that the polynomial evaluates to zero? (This is Hilbert's Tenth Problem, more under Matiyasevich's theorem.)

- Given a program, input parameters, and a prediction about whether it will eventually halt, is that prediction correct?

Another example of a problem that is not recursively enumerable is this:

- Given a program and input parameters, will that program run forever?

If *L* and *P* are two recursively enumerable languages, then the following languages are recursively enumerable as well:

- the Kleene star
*L*^{*}of*L* - the concatentation
*LP*of*L*and*P* - the union
*L*∪*P* - the intersection
*L*∩*P*