Autor Tema: Demostrar que MCD y MCM son recursivas primitivas

0 Usuarios y 1 Visitante están viendo este tema.

11 Diciembre, 2011, 06:26 pm
Leído 2561 veces

mtsr

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Estuve buscando la demostracion de ambas por Internet, pero no he tenido exito. Les agradeceria si me pueden pasar algun link con las demostraciones o escribirlas abajo.

Desde ya muchas gracias!

12 Diciembre, 2011, 09:45 am
Respuesta #1

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Esto se puede hacer de muchas formas distintas, dependiendo de los resultados previos que tengas. Una observación interesante es que \( mcm(n,m)=\frac{mn}{mcd(m,n)} \), así que si ya sabes que la multiplicación y la división entera son recursivas primitivas, solo necesitas encontrar una definición recursiva de \( mcd(m,n) \).

La manera más sencilla probablemente sea usando el algoritmo de Euclides. Para ello necesitas saber, aparte de que las funciones aritméticas básicas son recursivas primitivas, que el resto de una división de naturales, \( resto(m,n) \), es una función recursiva primitiva. Entonces, puedes definir mcd(m,n) de la siguiente manera:

\( mcd(m,n) = m  \), si \( n=0 \)
\( mcd(m,n) = mcd(n,resto(m,n)) \), si \( n \neq 0 \)

Debería ser claro que esto puede ser reescrito como una definición recursiva primitiva, y por el algoritmo de Euclides es claro que esto es realmente el máximo común divisor de m y n.

Saludos

12 Diciembre, 2011, 05:51 pm
Respuesta #2

mtsr

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Esta bastante claro, pero quisiera pedir si es posible que reescribas el mcd como una definicion recursiva primitiva, eso todavia no puedo visualizarlo del todo.

13 Diciembre, 2011, 09:23 am
Respuesta #3

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Es inmediato usando el "Course-of-values recursion", esto es, que la clase de funciones recursivas primitivas es cerrada bajo recursiones que involucran no solo el valor anterior de la función, sino todos los anteriores. Más formalmente, si definimos \( \bar{f}(x,y)=\langle f(x,0),...,f(x,y) \rangle \) y \( f(x,y) \) se define de la siguiente manera:

\( f(x,0)=g(x) \)
\( f(x,y+1)=h(x,y,\bar{f}(x,y)) \)

donde tanto g como h son recursivas primitivas, entonces también lo es f.

Para demostrar este teorema lo único que necesitas es ver que \( \bar{f} \) es recursiva primitiva (pues \( f(x,y)=(\bar{f}(x,y))_{y+1} \) donde \( ( )_{y+1} \) es la función de decodificación, que se puede tomar recursiva primitiva), y esto se ve con una recursión primitiva usual usando que la concatenación es recursiva primitiva.

En nuestro caso, hay algún detalle que hace que la recursión sea un poco más complicada de lo que pensaba en un principio (el hecho de que puedes tener m>n o m<n). Esto se puede solventar por ejemplo introduciendo una función auxiliar. Aplicando este esquema tendríamos (revísalo porque lo he pensado rápido):

\( mcd'(m,0)=m \)
\( mcd'(m,n+1) = (\bar{mcd'}(m,n))_{resto(n+1,m)} \) si \( resto(n+1,m)<n+1 \)
\( mcd'(m,n+1) = n+1  \) si \( resto(n+1,m)=n+1 \)

mcd' es recursiva primitiva. Finalmente,

\( mcd(m,n)=mcd'(max \{m,n \}, min \{m,n \}) \) es recursiva primitiva y la función buscada.

Si no te gusta mucho esta aproximación (que reconozco que ha sido un poco más liada de lo que preveía en un principio, aunque igual se puede hacer mucho más directo), puedes irte por el camino de definir máximo común divisor como el producto de los factores primos comunes a m y n elevados al menor exponente. Para esto necesitas saber un par de cosas sobre primos (la función primo(n) es recursiva primitiva, etc), divisibilidad es recursiva primitiva, productorios acotados son recursivos primitivos y minimización acotada de predicados recursivos primitivos es recursiva primitiva (esto último para definir el mayor exponente de p que divide a n).

Saludos