complejidad computacional de las funciones recursivas primitivas

Question

Si tenemos un sistema de reescritura para las funciones recursivas primitivas, que simplifica cada término según cómo se haya definido la función, ¿cuál es la complejidad computacional de este cálculo? Es decir, ¿cuál es la coplejidad del procedimiento de normalización? He oído decir que para un término cerrado el cálculo del valor de la función requiere una inducción transfinte hasta $\epsilon_0$ . ¿Es esto cierto y dónde puedo encontrar una prueba de ello?

Por ejemplo en (Schwichtenberg & Wainer 2012) hay un lema que dice que una función recursiva primitiva es computable en $F_{\alpha}$ -tiempo limitado, para algunos $\alpha<\omega$ donde el conjunto de todos los $F_{\alpha}$ para $\alpha<\epsilon_0$ es la jerarquía de crecimiento rápido.

¿Está relacionada la medida de la inducción transfinita con esta forma de acotar la complejidad?

Answer 1

Me parece que algunos aspectos de esta pregunta son difíciles de entender. Por ejemplo, la parte de "calcular el valor de la función requiere una inducción transfinita hasta $\varepsilon_0$ "parece confundir los métodos de prueba (como la inducción transfinita) con los métodos de cálculo. Además, gran parte (si no toda) de la pregunta parece referirse a los funcionales recursivos primitivos de tipo superior (como en la interpretación Dialéctica de Gödel) en lugar de a meras funciones recursivas primitivas. Por lo tanto, lo siguiente puede no ser lo que el OP estaba buscando, pero aquí va de todos modos:

No se puede decir mucho sobre la complejidad temporal del cálculo de funciones recursivas primitivas (de números naturales a números naturales), excepto que es recursiva primitiva y, por tanto, está limitada por un nivel finito $F_n$ de la jerarquía Grzegorczyk (esencialmente equivalente a la jerarquía de crecimiento rápido, creo).

Por otro lado, para los funcionales recursivos primitivos de tipo finito, se puede considerar el problema de la evaluación de términos de tipo 0 (es decir, términos que denotan números naturales). Aquí, el único límite que puedo ver para la complejidad temporal es el nivel $\varepsilon_0$ de la jerarquía Grzegorczyk. Para cualquier funcional recursivo primitivo fijo, la evaluación de sus valores numéricos tomaría un tiempo limitado por $F_\alpha$ para algunos $\alpha<\varepsilon_0$ pero los diferentes funcionales necesitarían diferentes $\alpha$ con ningún límite uniforme por debajo de $\varepsilon_0$ .

La relevancia del principio de prueba de la inducción transfinita hasta $\varepsilon_0$ (para fórmulas abiertas) es que esto es lo que se necesita, además de la aritmética recursiva primitiva, para demostrar que todo término cerrado de tipo 0, construido a partir de funcionales recursivos primitivos de tipo superior, puede ser reducido a un valor numérico.

Answer 2

En realidad, no hay necesidad de ninguna inducción transfinita. Una interpretación monótona produce que las longitudes de derivación para cualquier término fijo serán recursivas primitivas en los valores de los numerales introducidos. Tengo un artículo en APAL con Cichon sobre el tema y, además, un artículo en JSL sobre la T de Goedel en el que se muestra que para T se necesita una recursión epsilon_0 para demostrar la normalización fuerte mediante una interpretación monótona.

Lo mejor,

Andreas

Answer 3

Querido Andreas,

Sí, en efecto. Tenemos el siguiente hecho (no demasiado difícil): Sea S^m(0) el número de $m$ . Para cualquier término de ARP $t(x_1,\ldots,x_n)$ La longitud de la derivación de $t(S^{m_1}(0),\ldots,S^{m_n}(0))$ estará limitada por una primitiva recursiva (dependiendo de $t$ ) con argumentos $m_1,\ldots,m_n$ . (Aquí asumo sistemas de reescritura estándar para modelar la recursión primitiva).

Para los términos de la T de Gödel las longitudes de derivación se vuelven más complejas dependiendo del nivel de tipo de los términos en cuestión.

Mi conjetura general es que para clases subrecursivas C típicas (no demasiado pequeñas) las funciones de longitud de derivación para los términos en C no saldrán de C.

El resultado para la recursión primitiva no es difícil mientras que el resultado para la T de Gödel es algo complicado.

En el caso de los ARP, también hay una compensación en términos de ordenación de la terminación. La terminación de los sistemas de reescritura para las funciones prim rec se puede mostrar por el ordenamiento de trayectorias de conjuntos múltiples. Y las pruebas de terminación para el ordenamiento de trayectorias de conjuntos múltiples de la ruta del conjunto múltiple conducen a longitudes de derivación prim rec (resultado de Dieter Hofbauer). El resultado correspondiente para la recursión múltiple es uno de mis primeros resultados de mis primeros resultados en la teoría de reescritura de términos. Wilfried Buchholz dio una buena prueba teórica de estos resultados en APAL.

También hay una buena aplicación de la reescritura de términos a esquemas más complicados de la primitiva funciones recursivas primitivas. Por ejemplo, puede utilizarse para demostrar que las funciones prim rec son cerradas bajo recursión paramétrica, o recursión anidada simple, o incluso recursión múltiple no anidada.

Lo mejor, Andreas