Entre la recursión mu- y la primitiva

Question

Es bien sabido que la recursión primitiva no es lo suficientemente potente para expresar todas las funciones, siendo la función de Ackermann probablemente el ejemplo conocido.

Ahora bien, en los cursos de lógica (que he hecho ver) siempre se procedía de la recursión primitiva a la mu-recursión. En términos de ciencias de la computación, esto significa básicamente que estamos saltando de un formalismo en el que se garantiza que los programas se detendrán a un formalismo Turing-completo en el que la detención es una propiedad no computable, es decir, no podemos decir para cada programa si finalmente se detendrá.

Tengo curiosidad por saber si hay alguna jerarquía entre la recursión primitiva y mu-recursión. Después de un tiempo encontré un lenguaje de programación llamado Charity. En Charity (según Wikipedia) todos los programas tienen la garantía de parar, por lo que no es Turing-completo, pero, por otro lado, es lo suficientemente expresivo para implementar la función de Ackermann.

Esto sugiere que hay al menos un nivel entre la mu-recursión y la recursión primitiva.

Mi pregunta es: ¿existe algún otro formalismo de parada segura que sea más expresivo que la recursión primitiva? O, mejor aún, ¿existen algunas jerarquías conocidas entre las funciones mu-recursivas y las recursivas primitivas? Tengo curiosidad por saber cuánto podemos calcular con un formalismo que garantice la parada.

Answer 1

Creo que también sería razonable mencionar (explícitamente) las funciones definibles por recursión primitiva en tipos superiores - en lugar de definir únicamente funciones $\mathbb{N}\to\mathbb{N}$ mediante la recursión primitiva, también podemos definir familias de funciones (es decir, funciones $\mathbb{N}\to\mathbb{N^N}$ ) mediante la recursión primitiva (y, por supuesto, cosas aún más complicadas).

Como ejemplo, definamos primero una función de iteración $g\colon\mathbb{N}\times\mathbb{N^N}\to\mathbb{N^N}$ por recursión primitiva, por: \begin{array}{l} g(0,f) = i \qquad\qquad\text{(the identity function)}\\\\ g(n+1, f) = f\circ g(n, f) \end{array} Podemos entonces definir fácilmente una versión "acelerada" de la función de Ackermann como una función $A\colon\mathbb{N}\to\mathbb{N^N}$ , por: \begin{array}{l} A(0) = S \quad\quad\text{(successor)}\\\\ A(n+1) = g(n, A(n)) \end{array}

Esto es bastante popular entre (algunos grupos de) informáticos, en particular los interesados en la programación funcional, y alguna forma de recursión primitiva en tipos superiores está detrás de la fuerza del lenguaje Charity que has mencionado (que también permite la recursión primitiva sobre otras estructuras de datos que los números naturales).

Answer 2

La respuesta de Robin Chapman es muy oportuna. Esta es una respuesta teórica que señala una sutileza en la pregunta.

En primer lugar, recordemos que las funciones recursivas primitivas son la clase más pequeña de funciones sobre $\mathbb{N}$ eso:

• Incluye la función constante cero, la función sucesora y todas las funciones de proyección;
• es cerrado bajo composición;
• y se cierra bajo la recursión primitiva.

Llamemos a esta clase de funciones $\operatorname{PR}(\emptyset)$ . Para cualquier conjunto $A$ de funciones de teoría de números, podemos definir una clase más general $\operatorname{PR}(A)$ como la clase más pequeña de funciones que satisface las propiedades anteriores y también incluye cada función en $A$ .

Si cada función en $A$ es computable, entonces cada función en $\operatorname{PR}(A)$ es computable. Además, si cada función en $A$ es total entonces cada función en $\operatorname{PR}(A)$ es total.

Sería trivial, suponiendo que $A$ es finito (o, más generalmente, sólo explícitamente enumerado), para crear un lenguaje de programación tal que cada programa en el lenguaje calcule una función en $\operatorname{PA}(A)$ y cada función de este tipo tiene un programa en el lenguaje. El lenguaje simplemente tiene primitivas para todas las funciones en $A$ y para las funciones recursivas primitivas básicas, junto con los operadores para la composición y la recursión primitiva.

Por lo tanto, una respuesta a "Tengo curiosidad por saber cuánto podemos computar con un formalismo que garantice la detención" es "Para cualquier función total computable existe tal formalismo" y, más generalmente, esto es cierto para cualquier secuencia efectiva de funciones totales computables.

Lo principal que un sistema de este tipo no puede es una función universal, siempre que el sistema tenga algunas propiedades básicas de cierre.

Apéndice

Ya que varias personas han señalado lo mismo, puedo añadir algo de valor a la respuesta incluyendo la prueba estándar de mi observación sobre las funciones universales. Una función universal de dos lugares, para algún sistema, es una función $g(i,k)$ tal que para cada función de un lugar $f(k)$ en el sistema hay algún número natural $e$ con $\lambda k .f(k) = \lambda k. g(e,k)$ . Supongamos que $g$ es una función de este tipo; defina una función $h$ como $h(k) = g(k,k) + 1$ . Entonces $h$ tiene algún índice $e$ . Así, $g(e,e) = h(e)$ por la definición de $g$ et $e$ y $h(e) = g(e,e) + 1$ por la construcción de $h$ . Esto es imposible, por lo que cualquier sistema de funciones totales que me permita formar las funciones como $h$ no puede tener una función universal $g$ .

En particular, para cualquier clase de funciones $A$ y cualquier función $g(j,i)$ en $\operatorname{PA}(A)$ la función $h(n) = g(n,n)+1$ está en $\operatorname{PR}(A)$ . Así que esta clase no tendrá una función universal siempre que cada función en $A$ es total. Por supuesto, si dejas que $A$ sea el conjunto de todas las funciones parcialmente computables, entonces $\operatorname{PR}(A)$ es también el conjunto de todas las funciones parciales computables y, por tanto, contiene una función universal (que no es total).

Desde este punto de vista, la limitación no está en si se pueden incluir funciones computables particulares; la limitación está en la estructura interna de cualquier clase efectiva particular de funciones.

Answer 3

Puede buscar jerarquías de rápido crecimiento .

Answer 4

Se pueden considerar formalismos de programación en los que un programa es un par (M, P), siendo M una máquina de Turing y P una prueba de que M se detiene en todas las entradas. Entonces, si la prueba es correcta, (M, P)(x) = M(x); si es incorrecta, (M, P)(x) = 0.

Como alternativa, se puede considerar la recursión primitiva con una función "oráculo": así, por ejemplo, podemos permitir la función Ackermann en nuestros límites de recursión. Si utilizamos un oráculo recursivo primitivo, no ganamos potencia; pero mientras utilicemos una función computable, nuestras funciones siguen siendo computables. Esto debería dar una jerarquía con respecto a los oráculos, pero no estoy seguro de los detalles.

Answer 5

La clase PR de las funciones recursivas primitivas es la clase más pequeña de funciones que contiene unas pocas funciones simples (sucesoras, cero, proyección) y está cerrada bajo composición y definición de funciones por recursión.

Si $f:\mathbb{N}^k\to \mathbb{N}$ es cualquier función, se puede formar la clase $PR(f)$ de funciones que son recursivas primitivas en relación con $f$ simplemente añadiendo $f$ como una de las funciones simples y luego cerrando bajo composición y recursión. Si $f$ es total, entonces cada función en $PR(f)$ es total, y si $f$ es computable, entonces cada función en $PR(f)$ será computable. Esto equivale a utilizar $f$ como un oráculo, como mencionó Max. Aquí hay una clara jerarquía, porque si $f\in PR(g)$ entonces $PR(f)\subset PR(g)$ y esta jerarquía equivale a algo así como la jerarquía de los grados de Turing, pero con una recursión primitiva.

Más generalmente, para cualquier conjunto $F$ de funciones, podemos formar $PR(F)$ añadiendo todas las funciones en $F$ y el cierre bajo la composición y la recursión, y todavía tenemos la jerarquía que si $F\subset PR(G)$ entonces $PR(F)\subset PR(G)$ . Esta situación más general parece totalmente general, ya que si se tiene una clase $F$ de funciones que contienen todas las funciones recursivas primitivas y que son cerradas bajo composición y recursión, entonces $F=PR(F)$ y, por tanto, esta jerarquía parece capturar todas las clases que se pueden considerar.