Monografias.com > Matemáticas
Descargar Imprimir Comentar Ver trabajos relacionados

Funciones Primitivas Recursivas




Enviado por Pablo Turmero



  1. Composición
  2. Recursividad
  3. Clases PRC (Primitivas Recursivamente Cerradas)
  4. Algunas Funciones Recursivas Primitivas
  5. Predicados Recursivos Primitivos
  6. Operaciones Iteradas y Cuantificadores Iterados
  7. Minimización
  8. Funciones de emparejamiento y Números de G?del

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.

Monografias.com

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:

Monografias.com

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.-

Monografias.com

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

Monografias.com

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

Monografias.com

Clases PRC (Primitivas Recursivamente Cerradas)

Consideramos primero las llamadas funciones iniciales.

Estas son:

Monografias.com

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.

Monografias.com

Definición.- Una función se dice recursiva primitiva si puede obtenerse a partir de las funciones iniciales mediante recursión y composición.

Corolario.- La clase de las funciones recursivas primitivas es PRC.

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

Corolario.- Toda función recursiva primitiva es calculable.

El recíproco no es cierto.

Algunas Funciones Recursivas Primitivas

Monografias.com

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

Monografias.com

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

Monografias.com

y, por tanto, g es recursiva primitiva.

Monografias.com

Las ecuaciones de recursión son

xMonografias.com0 = x

xMonografias.com(t+1) = p(xMonografias.comt)

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

Esta función puede expresarse como

|x – y| = (xMonografias.comy) + (yMonografias.comx)

y, por tanto, es recursiva primitiva.

Monografias.com

Ejercicios

Monografias.com

___________________

Ejercicios Resueltos

3.-

Monografias.com

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

Monografias.com

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:

Monografias.com

Vamos a demostrar por inducción que es recursiva primitiva

Monografias.com

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

es primitiva recursiva

5.-

Podemos definir

Monografias.com

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

Monografias.com

10.- x = y

Este predicado corresponde a la función recursiva primitiva

Monografias.com

Teorema.

Monografias.com

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

11.- x < y

Solo hay que escribir

Monografias.com

Teorema (Definición por casos).

Monografias.com

Operaciones Iteradas y Cuantificadores Iterados

Teorema.

Monografias.com

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,

Monografias.com

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

Monografias.com

Esto lo expresamos con el siguiente corolario.

Monografias.com

Teorema.

Monografias.com

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

Monografias.com

13.- Primo (x)

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

Monografias.com

Ejercicios

Monografias.com

___________________

Ejercicios Resueltos

Monografias.com

Monografias.com

Minimización

Monografias.com

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

Teorema.

Monografias.com

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

Monografias.com

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

Monografias.com

Discutamos ahora la minimización no acotada. Definimos

Monografias.com

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.

Monografias.com

Ejercicios

Monografias.com

___________________

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

Monografias.com

Esta ecuación define pues dos funciones

Monografias.com

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

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

Monografias.com

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

Monografias.com

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

Monografias.com

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.

Monografias.com

Teorema.

Monografias.com

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

Monografias.com

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,

Monografias.com

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

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

Monografias.com

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

Monografias.com

Ejercicios

Monografias.com

__________________

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

Monografias.com

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

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter