Funciones recursivas

Vamos a ver como se construye una clase de funciones, llamadas recursivas primitivas, definidas entre n-uplas de números naturales sobre los números naturales ³¹, (es decir $f : N^n \rightarrow N$), con la idea de caracterizar las funciones que son efectivamente calculables, es decir, aquellas funciones para las que dada la n-upla de sus argumentos podemos definir un procedimiento para encontrar en un numero finito de pasos el valor de la función.

Usaremos para ello una definición recursiva, es decir, nos apoyaremos en un conjunto de funciones que por definición son recursivas (conjunto inicial que se denomina base de la recursión), y en un conjunto de reglas que aplicándolas a funciones recursivas primitivas ya definidas obtenemos nuevas funciones recursivas. En nuestro caso la base esta formada por las funciones nula, sucesor y proyección, y las reglas que llamamos de composición y de recursión primitiva. Estos elementos quedan definidos de la siguiente forma:

Base de recursión:

Función nula $N(x) = 0$ :

mediante la que se hace corresponder a cualquier numero natural el numero 0 (borrar el numero).

Función sucesor $S(x) = x'$ :

mediante la cual a cada numero natural $x$ se le hace corresponder su sucesor, que denotamos por $x'$ (encontrar el siguiente).

Función proyección $I^n_i (x_1 , x_2 , \ldots x_i, \ldots x_n) = x_i$ :

mediante la cual a cada n-upla se le hace corresponder su i-esima componente (elegir uno de una sucesión finita)

$\newline$

Reglas:

Regla de composición :

dadas las funciones

$$g_i (x_1 , x_2 , . . ., x_n), \qquad(i=1, 2, . . . m)$$

y la función $f$ que depende de las $m$ funciones anteriores, es decir

$$f = (g_1 , g_2 , . . ., g_m),$$

entonces decimos que

$$h (x_1 , x_2 , . . . , x_n)$$

es la función compuesta de las $g_i$ mediante $f$ si está definida de la siguiente forma:

$$h (x_1 , x_2 , . . ., x_n) = f (g_1 (x_1 , x_2 , . . ., x_n... ... (x_1 , x_2 , . . . , x_n), . . . g_m (x_1 , x_2 , . . ., x_n))$$

Regla de recursion primitiva con parametros:

dadas dos funciones recursivas conocidas

$$f (x_1 , x_2 , . . ., x_n),$$

$$g (y, x_1 , x_2 , . . ., x_n , z),$$

que dependen de los parámetros $x_1 , x_2 , . ., x_n$ , se define la función

$$h (y, x_1 , x_2 , . ., x_n),$$

mediante el siguiente esquema de recursión:

$$h (0, x_1 , x_2 , . . ., x_n) = f (x_1 , x_2 , . . ., x_n)$$

$$h (y', x_1 , x_2 , . . ., x_n) = g (y, x_1 , x_2 , . . ., x_n , h(y, x_1 , x_2 , . . . , x_n))$$

Regla de recursion primitiva sin parametros:

es un caso particular del anterior en el que no aparecerán los parámetros y el esquema de recursión sería:

$$h (0) = k$$

$$h (y') = g (y, h(y))$$

donde $g(y, z)$ es una función recursiva conocida y $k$ es una constante (un numero natural dado).

La clase de funciones definidas de esta manera, es una clase de funciones que se puede calcular efectivamente, ya que son construidas a partir un conjunto base, cuyo cálculo puede ser considerado trivial, y mediante procedimientos o esquemas de cálculo sencillos y que se realizan por pasos sucesivos ³². Se prueba que esta clase de funciones es la misma que la que se define utilizando para ello las Maquinas de Turing, que describimos a continucion.