Siguiente: Problema de la parada Un nivel arriba: Teoría de la recursividad Anterior: Teoría de la recursividad

Funciones recursivas

Definición. La clase de las funciones recursivas es la mínima clase de funciones que contiene a las funciones recursivas primitivas y que es cerrada por el esquema de minimización (no necesariamente acotada).


Ejemplos. Los siguientes son ejemplos de funciones recursivas:

1.

Todas las funciones recursivas primitivas son recursivas.

2.

La función de Ackermann es recursiva pero no es recursiva primitiva. Efectivamente, en la sección 2.4 vimos que la función de Ackermann se calcula reiterando el operador T definido por la relación 2.9 de esa misma sección, hasta la primera vez que se obtenga una lista de longitud 1. El operador T es recursivo primitivo y la reiteración hasta la condición terminal se puede realizar mediante el esquema de minimización.

Teorema 1.1   Las siguientes clases de funciones coinciden

• las funciones recursivas,
• las funciones computables,
• las funciones calculables por máquinas de Turing.

En efecto, por un lado, toda función recursiva es computable pues las funciones básicas, a saber la operación 0, la sucesor y las proyecciones, son todas computables y los esquemas de composición, de recursión y de minimización son programables mediante programas-while . Por otro lado, toda función computable es recursiva pues las funciones 0, sucesor y antecesor y la noción de asignación son representables mediante funciones recursivas. Luego, si P₁ y P₂ fuesen dos programas que calculen sendas funciones computables, entonces las funciones computadas por los programas y son también representables mediante funciones recursivas, la última utilizando ciertamente el esquema de minimización.


Ya que la clase de funciones computables se autorrepresenta, tenemos como una consecuencia la siguiente

Proposición 1.1   La clase de funciones recursivas se autorrepresenta, es decir, existe una función universal para esta clase que es en sí recursiva:

$$\begin{eqnarray*}\mbox{\it eval}:N^2 &\rightarrow& N \\ (k,m) &\mapsto& f_k(m)... ... el valor en $m$\space de la $k$ -\'esima funci\'on recursiva.} \end{eqnarray*}$$

El lema de la diagonal asevera que la subclase de funciones recursivas totales no se autorrepresenta.
Siguiente: Problema de la parada Un nivel arriba: Teoría de la recursividad Anterior: Teoría de la recursividad