Enumeración de los niveles de la jerarquía de Grzegorczyk

Question

Grzegorczyk ha dividido la clase de funciones recursivas primitivas a la jerarquía de Grzegorczyk por su tasa de crecimiento. En esta jerarquía $E_i\subset E_{i+1}$ y la relación de subconjuntos es estricta. También $\cup_{i}E_i = Pr$ es decir, la unión de todos los niveles es igual a la clase de funciones recursivas primitivas.

Sé que las funciones recursivas primitivas son recursivamente enumerables, pero me pregunto si los niveles de la jerarquía de Grzegorczyk son recursivamente enumerables, es decir, si es posible "recorrer" algún nivel $E_i$ o, mejor aún, funciones en $E_i\setminus E_{i-1}$ ?

Answer 1

La definición habitual de $E_n$ es en términos de funciones básicas, el $n$ función generadora, cerrada bajo composición, y recursión acotada. Supongo que ves cómo una enumeración podría construirse fácilmente a partir de una especie de árbol sintáctico, excepto por la dificultad de que la restricción en el esquema de recursión acotada no es sintáctica. Una idea sencilla que se me ocurre es sortear esto reformulando la restricción del esquema, por ejemplo, dado $f$ , $g$ , $h$ , defina $j$ : $$j(x,0) = min(h(x,0),f(x))$$ $$j(x,n+1) = min(h(x,n+1),g(x,j(x,n)))$$ Por lo tanto, no hay ninguna restricción sintáctica sobre la recursión acotada, pero el valor de la nueva función $j$ sigue estando semánticamente limitada por la función anterior $h$ y, por lo tanto, estoy bastante seguro de que esto es equivalente al esquema habitual de recursión acotada.

También existen caracterizaciones alternativas de los niveles de la jerarquía de Grzegorczyk que son más naturalmente sintácticas y a partir de las cuales se puede construir fácilmente una enumeración. Tengo en mente la caracterización de Marc Wirz en términos de recursión segura .

Para obtener una enumeración de $E_{n+1} \setminus E_n$ tiene el siguiente problema: definir $f(m) = 0$ si Conjetura de Goldbach tiene capacidad para $m$ Si no es así $f(m)$ es igual al $m$ El valor de la $n+1$ 'st función generadora. Ahora sintácticamente vemos $f \in E_{n+1}$ pero semánticamente vemos $f$ es constante-cero (por lo tanto en $E_0$ si la conjetura de Goldbach es verdadera. Estoy bastante seguro de que esta idea se puede convertir en un teorema de imposibilidad.

Answer 2

He publicado una versión desarrollada de la respuesta anterior a esa pregunta. Está contenida en el libro "AVANCES Y APLICACIONES DE SISTEMAS INTELIGENTES Y NUEVAS TECNOLOGIAS", CONSEJO DE PUBLICACIONES DE LA UNIVERSIDAD DE LOS ANDES, 2016 con el título "LA CLASE 0 DE LA JERARQUIA DE GZREGORCZYK ES RECURSIVAMENTE ENUMERABLE".

Sin embargo, siempre me he preguntado por qué el citado artículo de Wirz sobre la recursión segura fue rechazado para su publicación. A mi entender, parece totalmente correcto y representa un punto clave en las caracterizaciones de las jerarquías recursivas.