PR es la clase de complejidad de todas las funciones recursivas primitivas o, de manera equivalente, el conjunto de todos los lenguajes formales que pueden decidirse en el tiempo delimitados por dicha función. Esto incluye suma , multiplicación , exponenciación , tetración , etc.
La función de Ackermann es un ejemplo de una función que no es recursiva primitiva, lo que muestra que PR está estrictamente contenida en R (Cooper 2004: 88).
Por otro lado, podemos "enumeración" cualquier conjunto recursivamente numerable (véase también la clase de complejidad RE ) por una función primitiva recursiva en el sentido siguiente: dada una entrada ( H , K ), donde M es una máquina de Turing y k es un número entero, si M se detiene dentro de k pasos, entonces la salida M ; de lo contrario, no generará nada. Entonces la unión de las salidas, sobre todas las posibles entradas ( M , k ), es exactamente el conjunto de M que se detienen.
PR contiene estrictamente ELEMENTARY .
PR no contiene problemas de "PR-completo" (asumiendo, por ejemplo, reducciones que pertenecen a ELEMENTARY). En la práctica, muchos problemas que no están en las relaciones públicas, sino más allá, son-completo (Schmitz 2016).
Referencias
- S. Barry Cooper (2004). Teoría de la computabilidad . Chapman y Hall. ISBN 1-58488-237-9.
- Herbert Enderton (2011). Teoría de la computabilidad . Prensa académica. ISBN 978-0-12-384-958-8.
- Schmitz, Sylvain (2016). "Jerarquías de complejidad más allá de lo elemental". Transacciones ACM en la teoría de la computación . 8 : 1–36. arXiv : 1312.5686 . doi : 10.1145 / 2858784 .
enlaces externos
- Complejidad Zoo : PR .