Funciones recursivas

Una segunda definición de computabilidad, muy diferente de la que usa máquinas de Turing, es la función parcial recursiva. Las funciones parciales recursivas están construídas a partir de la función sucesor \(s : \mathbb{N} \to \mathbb{N}\), \(s(n):=n+1\) y la recursión: una forma de definir funciones en los naturales de modo que el valor de \(f(n)\) depende de los valores \(f(m)\) para \(m < n\).

Por ejemplo, la sucesión de números de Fibonacci usualmente se define como sigue:

• \(F(0) = 0\)
• \(F(1) = 1\)
• Para \(n>1\), \(F(n) = F(n-1) + F(n-2)\).

Podemos considerar esas tres ecuaciones como un sistema de ecuaciones cuya incógnita es una función \(F : \mathbb{N} \to \mathbb{N}\). El sistema de ecuaciones tiene solución única: \(F(n)\) tiene que ser el \(n\)-ésimo número de Fibonacci. Para probar que la solución es única se puede usar inducción matemática.

La recursión y la inducción están estrechamente relacionadas: la recursión es una forma de definir funciones que dependen de sus valores anteriores, y se puede demostrar que la definición produce una única función usando inducción.

Más adelante daremos la definición precisa de función parcial recursiva \(\mathbb{N}^{k} \to \mathbb{N}\) y también de una noción más restrictiva de función recursiva primitiva, pero primero, con lo que ya dijimos sobre el estilo de la definición, contrastémosla con la definición de Turing-computable.

Esta definición de función recursiva le da un lugar privilegiado a la aritmética:

• Es solo para funciones \(\mathbb{N}^{k} \to \mathbb{N}\), mientras que con máquinas de Turing podíamos definir funciones computables de sucesiones de símbolos a sucesiones de símbolos. Conversamente, para usar máquinas de Turing para definir funciones computables en los naturales, teníamos que codificar los números con símbolos de alguna forma (por ejemplo con notación binaria).
• La función sucesor, que es la base de la aritmética, es recursiva por decreto. Las máquinas de Turing no «saben nada sobre aritmética».
• La operación básica para producir funciones recursivas nuevas a partir de otras anteriores es dar una definición recursiva; el que este estilo de definición realmente produce funciones bien definidas está estrechamente relacionado con la inducción, que es el principio lógico básico en la aritmética.

Esto nos dice que estas dos definiciones de computabilidad, la de función recursiva y la que usa máquinas de Turing, son de sabores muy diferentes. Aún así, resultan equivalentes, que es una constante en este tema: intentos diferentes de captar al escencia de lo computable llevan a resultados equivalentes.

Hay un subconjunto de las funciones parciales recursivas que definiremos primero.

Las siguientes funciones son recursivas primitivas por decreto:

• La función sucesor \(s : \mathbb{N} \to \mathbb{N}\) dada por \(s(n):=n+1\).
• Las funciones constantes: para cualquier \(k\) y \(m\), la función \(c_{m} : \mathbb{N}^k \to \mathbb{N}\) dada por \(c_{m}(n_{1}, \ldots, n_{k}) := m\).
• Las proyecciones coordenadas: para cualquier \(k\) e \(1 \le i \le k\) la función \(p_{i} : \mathbb{N}^{k} \to \mathbb{N}\) dada por \(p_{i}(n_{1}, \ldots, n_{k}) := n_{i}\).

Hay mecanismos para producir funciones primitivas recursivas nuevas a partir de funciones que ya sabemos que son primitivas recursivas:

Composición

Dadas funciones primitivas recursivas \(g : \mathbb{N}^{m} \to \mathbb{N}\), \(h_{1}, \ldots, h_{m} : \mathbb{N}^{k} \to \mathbb{N}\), la función \(f : \mathbb{N}^{k} \to \mathbb{N}\) dada por \(f(n_{1}, \ldots, n_{k}) := g(h_{1}(n_{1}, \ldots, n_{k}), \ldots, h_{m}(n_{1}, \ldots, n_{k}))\) es también recursiva primitiva.

Recursión

Dadas funciones recursivas primitivas \(g : \mathbb{N}^{k} \to \mathbb{N}\) y \(h : \mathbb{N}^{k+2} \to \mathbb{N}\) entonces la siguiente definición recursiva produce una función recursiva primitiva \(f : \mathbb{N}^{k+1} \to \mathbb{N}\):

• \(f(x_{1}, \ldots, x_{k}, 0) = g(x_{1}, \ldots, x_{k})\)
• \(f(x_{1}, \ldots, x_{k}, x+1) = h(x_{1}, \ldots, x_{n}, x, f(x_{1}, \ldots, x_{n}, x))\).

Finalmente, para concluir la definición, hay que decir que una función solo es recursiva primitiva si se puede obtener a partir de las funciones que fueron decretadas como tales a través de una serie de pasos de composición y recursión. En otras palabras, el conjunto de funciones recursivas primitivas es el menor conjunto de funciones que incluye el sucesor, las constantes y las proyecciones y que es cerrado bajo composición y recursión.

No cualquier función computable es primitiva recursiva. Las funciones primtivas recursivas corresponden intuitivamente a funciones que solo tienen ciclos cuyo número de pasos se puede acotar de antemano. Noten también que una función recursión primitiva es total, es decir, está definida en todos los elementos de \(\mathbb{N}^{k}\) si es una función de \(k\) variables.

Para obtener las funciones parciales recursivas a partir de las recursivas primtivas solo necesitamos agregar una operación más a las dos que ya teníamos de composición y recursión: la de búsqueda no acotada.

Búsqueda no acotada

Si \(g : \mathbb{N}^{k+1} \to \mathbb{N}\) es una función parcial recursiva, entonces la función \(f : \mathbb{N}^{k} \to \mathbb{N}\) definida como sigue también es parcial recursiva: \(f(n_1, \ldots, n_{k})\) es el mínimo valor de \(n\) tal que:

• \(g(n_{1}, \ldots, n_{k}, m)\) está definido para toda \(m \le n\), y
• \(g(n_{1}, \ldots, n_{k}, n) = 0\).

Entonces las funciones parciales recursivas son el menor conjunto de funciones que incluye al sucesor, las constantes y las proyecciones y que es cerrado bajo las operaciones de composición, recursion y búsqueda no acotada.

La búsqueda no acotada podría nunca terminar, por eso algunas funciones recursivas son parciales: se pueden quedar atrapadas en una búsqueda que nunca termina. La interpretación de la búsqueda como procedimiento de cálculo es como sigue:

1. Sea \(n=0\).
2. Calculamos \(g(n_{1}, \ldots, n_{k}, n)\).
3. Si el resultado fue \(0\), la respuesta es \(n\).
4. Si no, aumentamos \(n\) en \(1\) y regresamos al paso 2.

Si \(g\) es parcial, nos podemos quedar atorados en el paso 2. Y aunque \(g\) fuera total, si nunca vale \(0\), el procedimiento podría nunca terminar.

Las funciones parciales recursivas se pueden expresar en términos de funciones recursivas primitivas y el operador de minimización \(\mu\), que es una especie de cuantificador, como lo son \(\forall\) y \(\exists\). Dada una afirmación \(P(n)\) que depende de un natural \(n\), la expresión \(\mu n \; P(n)\) denota al mínimo valor de \(n\) tal que \(P(n)\) es cierto.

El cuantificador \(\mu\) permite definir concisamente varias funciones. Por ejemplo \(\lfloor \sqrt{m} \rfloor = \mu n (n^{2}>m) - 1\).

• ¿Cómo exactamente se usa inducción para probar que una función recursiva realmente define una única función? Piensa por separado en la existencia y la unicidad de una función que cumpla de la relación de recurrencia.
• ¿Por qué las funciones aritméticas normales como \(x+y, xy, x^{y}, x \ominus y\) son primitivas recursivas? (Recuerda que \(x \ominus y\) se define como \(x-y\) si \(x \ge y\) y como \(0\) si \(x < y\)).
• ¿Por qué las funciones recursivas primitivas son totales?
• Da ejemplos de funciones recursivas primivas que no son totales.
• ¿La función \(n \mapsto \lfloor \sqrt{n} \rfloor\) es primitiva recursiva como sugiere el ejemplo de la sección anterior? ¿Es recursiva primitiva?

• Rebecca Weber, Computablity Theory, sección 3.3, p. 50–55