Aunque existen varias definiciones equivalentes, ésta es una de las principales:

1. Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo caso se requiere que la máquina de Turing pare en todos los casos.

Todos los lenguajes regulares, independientes de contexto, dependientes de contexto y recursivos son recursivamente enumerables.

Los lenguajes recursivamente enumerables son cerrados con las siguientes operaciones. Esto es, si ${\displaystyle L}$  y ${\displaystyle P}$  son dos lenguajes recursivamente enumerables, entonces los siguiente lenguajes son recursivamente enumerables también:

• el cierre estrella ${\displaystyle L^{*}}$  de ${\displaystyle L}$ 
• la concatenación ${\displaystyle L\circ P}$  de ${\displaystyle L}$  y ${\displaystyle P}$ 
• la unión ${\displaystyle L\cup P}$  de ${\displaystyle L}$  y ${\displaystyle P}$ 
• la intersección ${\displaystyle L\cap P}$  de ${\displaystyle L}$  y ${\displaystyle P}$ 

Nótese que los lenguajes recursivamente enumerables no son cerrados con la diferencia ni el complementario.

• ${\displaystyle L\setminus P}$  puede no ser recursivamente enumerable
• ${\displaystyle {\bar {L}}}$  es recursivamente enumerable si y solo si ${\displaystyle L}$  es también recursivo.

• Lenguaje recursivo