Funciones Primitivas Recursivas

Vamos a ver como se construye una clase de funciones, llamadas primitivas recursivas, definidas entre n-uplas de números naturales sobre los números naturales, (es decir f: Nn ( 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 la función nula, sucesor y proyección, y las reglas que llamamos de composición y de recursión primitiva.

Composición

Vamos a considerar formas de combinar funciones calculables de forma que el resultado sea también calculable. Vamos a emperezar con la composición.

Las funciones f, g1,…,gk no necesitan ser totales. Si lo son la función composición también lo será.

Ejemplo.- Si f(x, y, z) = (x+ y).z

g1(x1, x2) = x1 – x2

g2(x1, x2) = x1. x2

g3(x1, x2) = x1 + x2

entonces

h(x1, x2) = f (x1 – x2, x1 . x2, x1 + x2) = (x1 – x2 + x1 . x2)( x1 + x2)

Teorema.- Si h es la composición de las funciones (totalmente) calculables f, g1,…,gk, entonces h es (totalmente) calculable.

Demostración.-

Sólo hay que considerar el siguiente programa que, obviamente, calcula h:

Así, como sabemos que las funciones x, x+y, x.y, x-y son calculables. Así mediante este teorema se puede deducir que 2x = x + x, 4×2 = (2x)(2x), son calculables.

También son calculables, 4×2 + 2x, 4×2 – 2x. También son totales, aunque la última se obtiene como composición de la función no total x – y, con 4×2 y 2x.

Recursividad

Supongamos que k es un número y

h(0) = k,

h(t+1) = g(t, h(t))

donde g es una función total de dos variables. Se dice que h se obtiene a partir de g, mediante recursividad.

Teorema.- Si h se obtiene a partir de g mediante recursividad, y g es calculable, entonces h es también calculable.

Demostración.-

Existe una recursión un poco más complicad, en el sentido de que implica funciones de más variables. Hay que partir de dos funciones totales, una f de n variables, y otra g de n+2 variables. Se dice entonces que la función h de n+1 variables se obtiene por recursión a partir de f y g si

Otra vez se verifica un teorema análogo al anterior.

Teorema.- Si h se obtiene a partir de f y g mediante las expresiones anteriores y f, g son calculables. Entonces h es también calculable.

Demostración.-

Sólo hay que tener en cuenta el siguiente programa

Clases PRC (Primitivas Recursivamente Cerradas)

Consideramos primero las llamadas funciones iniciales.

Estas son:

Inmediatamente tenemos el teorema siguiente.

Teorema.- La clase de las funciones calculables es PRC.

Demostración.-

Sólo hay que demostrar que las funciones iniciales son calculables.

Teorema.- Una función es recursiva primitiva si y sólo si pertenece a todas las clases PRC.

El recíproco no es cierto.

Algunas Funciones Recursivas Primitivas

luego se puede obtener a partir de composición y recursión de funciones primitivas y por tanto se recursiva primitiva.

2.- x . y

Las ecuaciones de recursión son

donde f es la función suma.

Por tanto, h, la función producto, es primitiva recurisiva.

3.- x!

Las ecuaciones de recursión son

y, por tanto, g es recursiva primitiva.

Las ecuaciones de recursión son

x0 = x

x(t+1) = p(xt)

7.- |x – y|, la función valor absoluto.

Esta función puede expresarse como

|x – y| = (xy) + (yx)

y, por tanto, es recursiva primitiva.

Ejercicios

___________________

Ejercicios Resueltos

3.-

Vamos a comprobar como se calcularía H(x+1) con unos cuántos ejemplos:

Con lo que se podría calcular de forma encadenada o recursiva poniendo como caso Base H(0) = 0.Pero de esta manera no podríamos demostrar que es recursiva primitiva, pero si lo expresamos de la siguiente manera:

H(0) = 0

H(x+1) = H(x) + E(x)

Y como E(x) es recursiva primitiva, ya que lo hemos demostrado anteriormente. H(x) es recursiva primitiva.

4.-

Vamos a ver como se comporta la función con algunos ejemplos:

Vamos a demostrar por inducción que es recursiva primitiva

Y como f es composición de operaciones que son primitivas recursivas, f

es primitiva recursiva

5.-

Podemos definir

de manera que como F es recursiva primitiva si definimos f a partir de F, por composición f es recursiva primitiva.

f(x) = F(x-1, x)

Con lo que ya está demostrado que f es recursiva primitiva.

Algunos ejemplos,

f(0) = F(0,0)

f(1) = F(0,1) = 1

f(2) = F(1,2) = 22

6.-

f no puede ser recursiva primitiva debido a que no es una función total, ya que cuando y

7.-

f si es primitiva recursiva, ya que al ser la resta acotada, la función si está definida cuando y

8.-

f si es primitiva recursiva, porque con x=0, al multiplicar por cero, f vale cero, y la función si está definida.

9.-

f si es primitiva recursiva porque es composición de funciones primitivas recursivas.

Predicados Recursivos Primitivos

Recordemos que los predicados son funciones totales que toman los valores 0 y 1. Por tanto, si los predicados están definidos sobre los números naturales, podemos hablar de predicados recursivos primitivos. Vamos a dar algunos predicados que son recursivos primitivos.

9.- x = y

Este predicado es una función que toma el valor 1 si x e y son iguales y 0 si son distintos. Es decir, corresponde a la función

10.- x = y

Este predicado corresponde a la función recursiva primitiva

Teorema.

Como consecuencia de este teorema, es inmediato demostrar que el siguiente predicado es recursivo primitivo.

11.- x < y

Solo hay que escribir

Teorema (Definición por casos).

Operaciones Iteradas y Cuantificadores Iterados

Teorema.

Demostración.-

Se podría intentar esta demostración por inducción. Así se podría demostrar que las funciones

g(0, x1,…,xn), g(1, x1,…,xn), …

pertenecen a f, pero no que la función g(y, x1,…,xn), en la función y es un argumento, pertenece a f.

La demostración de que g pertenece a f se basa en las siguientes ecuaciones de recursión,

Algunas veces la sumatoria o producto se realiza desde 1, en vez de desde 0. Es decir, se considera

Esto lo expresamos con el siguiente corolario.

Teorema.

A partir de estas propiedades, podemos construir algunas funciones recursivas primitivas como las siguientes.

12.- x|y. Relación divisor

Este predicado es recursivo primitivo, ya que puede expresarse como

13.- Primo (x)

El predicado "x es primo" es recursivo primitivo, ya que puede expresarse como

Ejercicios

___________________

Ejercicios Resueltos

Minimización

Usando este hecho y los teoremas anteriores es fácil demostrar el siguiente teorema:

Teorema.

Este teorema nos permite considerar los siguientes ejemplos de funciones recursivas primitivas.

14.- [x/y]

15.- R(x,y). Resto de la división entera.

Como

x/y = [x/y] + R(x,y)/y,

podemos escribir

R(x,y) = x

(y.[x/y])

por lo que R(x,y) es recursiva primitiva.

Notemos que R(x,0) = x.

16.- pn, n-ésimo número primo.

Para esta función se considera p0 = 0 y p1 = 2, p2 = 3,…

Consideremos las ecuaciones de recursión

Esta demostración está basada en cuna dada por Euclides para probar que existen infinitos números primos.

Vamos a escribir ahora las ecuaciones de recursión de una forma que nos muestre que pn es efectivamente una función recursiva primitiva. Primero notemos que

Discutamos ahora la minimización no acotada. Definimos

Respecto a esta función, indicaremos que existen predicados recursivos primitivos cuya minimización no acotada es total, pero no es recursiva primitiva. Sin embargo, se puede demostrar el siguiente teorema.

Teorema.

Ejercicios

___________________

Ejercicios Resueltos

Autoreferencia

La autoreferencia argumenta hechos que no pueden existir o que se referencian a sí mismo.

La autoreferencia se usa para demostrar en matemáticas, filosofía … que algo no se puede demostrar o no se puede definir.

La mejor manera de explicar la autoreferencia es a partir de un ejemplo.

"Esta frase es mentira", no hay manera de verificar su veracidad o su falsedad, debido a que se autoreferencia, con lo que si conseguimos que un problema se autoreferencie lograremos verificar que es indemostrable.

Funciones de emparejamiento y Números de Gödel

En esta sección estudiaremos dos procedimientos de codificación que usan funciones recursivas primitivas. El primero es para codificar pares de números por números simples. El segundo es para codificar listas de números.

Definiremos la función recursiva primitiva

Esta ecuación define pues dos funciones

Resumimos las propiedades de las funciones , l(z) y r(z) en el siguiente teorema.

Teorema (Teorema de la función de emparejamiento).

Otro apartado importante al igual que la codificación de pares de números es la descomposición de un número en un par de números. Nosotros sabemos que un par de números = a.

Con lo que tenemos que llegar a partir de "a", a obtener los valores x e y. Si nos fijamos en la fórmula descrita anteriormente, nos fijamos que x, sería el valor del exponente que acompaña al 2 al descomponer a+1 en factores primos, y el valor de y, sería

A continuación, un ejemplo de decodificación = 19

A continuación obtenemos funciones recursivas primitivas que codifican y decodifican sucesiones arbitrarias finitas de números. El método que usamos fue empleado por primera vez por Gödel, y depende de la descomposición en números primos de los enteros.

Teorema.

Este resultado es una consecuencia inmediata del teorema de unicidad de la factorización de enteros en productos de números primos (teorema fundamental de la aritmética).

Sin embargo, notemos que

El mismo resultado se verifica para cualquier sucesión finita de ceros añadidos a la derecha de una sucesión finita. El número de Gödel 1 se considera como representación de la sucesión vacía de longitud cero.

También hay que hacer notar que los ceros añadidos a l izquierda si cambian el número de Gödel de una sucesión. Por ejemplo,

En el siguiente toerma se resumen las propiedades fundamentales de estas funciones recursivas primitivas.

Teorema (Teorema de las Sucesiones de Números).-

La decodificación de una lista de números a diferencia de un par de números es más simple, ya que se haría de la siguiente manera

Suponemos el número 200

Ejercicios

__________________

Ejercicios Resueltos

1.-

Definimos la función H(n), que agrupa la sucesión de Fibonacci que es un par de números en uno sólo

3.-

b)

Definimos una función que codifique la sucesión de números como uno. Para ello definimos la función H(n)

Autor:

Pablo Turmero