PR (complejidad)
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.[1]
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.[2]
Por otro lado, es posible "enumerar" cualquier conjunto recursivamente enumerable (véase también su clase de complejidad RE) 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.
Referencias editar
- ↑ Herbert Enderton (2011). Computability Theory. Academic Press. ISBN 978-0-12-384-958-8.
- ↑ S. Barry Cooper (2004). Computability Theory. Chapman & Hall. p. 88. ISBN 1-58488-237-9.
Enlaces externos editar
- Complexity Zoo: PR.
Datos: Q841343
