PR

PR Es la clase de complejidad de todas las funciones recursivas primitivas o, de forma equivalente, el conjunto de todos los lenguajes formales que pueden ser decididos por tales funciones. Esto incluye adición, multiplicación, exponenciación, tetración, etc.​ La función de Ackermann es un ejemplo de una función que no es primitiva recursiva, y permite demostrar que PR está estrictamente contenida en R.​ Por otro lado, es posible "enumerar" cualquier conjunto recursivamente enumerable (véase también su clase de complejidad ) con una función primitiva recursiva en el sentido siguiente: dado una entrada (M, k), en donde M es una máquina de Turing y k es un entero, si M se detiene en k pasos o menos entonces su respuesta es M; en caso contrario no produce resultado. Entonces la unión de las respuestas, de todas las entradas posibles (M, k), es exactamente el conjunto de las máquinas M que terminan en tiempo finito. PR contiene estrictamente a la clase ELEMENTARY.