Es decir, un lenguaje formal es recursivo si existe una máquina de Turing que siempre se detiene cuando dada una secuencia finita de símbolos del alfabeto del lenguaje —llamada cadena de caracteres o palabra— como entrada, acepta solo esas palabras que son parte del lenguaje y rechaza todas las otras palabras.
La clase de todos los lenguajes recursivos es a menudo llamada R, aunque este nombre también es usado para la clase RP.
Todos los lenguajes regulares, libres de contexto y sensibles al contexto son lenguajes recursivos.
Los lenguajes recursivos son cerrados bajo las siguientes operaciones.
Sean L y P lenguajes recursivos, entonces los siguientes lenguajes son recursivos: La última propiedad viene del hecho que el conjunto diferencia puede ser expresado con intersecciones y complementos.