a recursively enumerable language

Now picture a librarian who is honest but not always punctual. If you ask for a book the library owns, she will eventually wave it in the air and say YES — maybe after a long search, but she will say it. If you ask for a book the library does NOT own, she might say NO, or she might keep searching the shelves forever, never coming back. So a YES always arrives in finite time, but a NO is not guaranteed. A recursively enumerable language is the set of strings such a one-sided machine accepts.

Formally, a language L is recursively enumerable (RE), also called TURING-RECOGNIZABLE, if some Turing machine M recognizes it: for every string w ∈ L, M run on w eventually halts and accepts; for every w not in L, M either halts and rejects OR runs forever (loops). The machine is allowed to loop precisely on the strings outside L. So acceptance is a reliable signal — if you ever see 'accept', the answer is truly YES — but the absence of acceptance can mean either 'no' or 'not finished yet', and you can never tell which from the outside.

Every recursive (decidable) language is recursively enumerable — a machine that always halts certainly recognizes its language — so RE is a strictly larger box that contains all the decidable languages and more. The famous extra inhabitant is the acceptance problem for Turing machines (does machine M accept input w?), which is recognizable but not decidable. The name 'recursively enumerable' comes from a beautiful equivalent view: L is RE exactly when some machine can print out, one by one, every string in L — it can ENUMERATE its members, even if it never finishes.