Autor Tema: Esquema Recursión Primitiva

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

25 Abril, 2011, 06:12 pm
Leído 2200 veces

gonchi1207

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 29
  • Karma: +0/-0
  • Sexo: Masculino
Buenas,


Bueno me gustaría saber si alguien sería tan amable de ayudarme a entender este básico concepto. Ya que lo he leído del teórico muchas veces y no logro entenderlo. También busqué en internet información acerca de este tema y no encontré nada, incluso en este foro si busco " recursión primitiva " me da 0 posts.

Yo no pude asistir al teórico cuando se dictó entonces solo me queda estudiar de las diapositivas. Subí la definición que da en las diapositivas en un archivo adjunto. Lo que no entiendo es Fs qué función es, y como se llega a esa afirmación. Y luego lo que me gustaría saber es que pasos tengo que tomar yo si teniendo un conjunto inductivo quiero hallar su esquema de recursión primitiva.

Por ejemplo a ver si alguien me puede ayudar con esto:

Hallar el esquema de recursión primitiva de :

I:
\( {- }0 \in{} I  \)
\( {- }Si n \in{} I  \longrightarrow{} n + 3 \in{} I  \)

O
\( {- }1000 \in{} O \)
\( {- }900 \in{} O \)
\( {- SI n }\in{} O \longrightarrow{} \sqrt[ ]{n} \in{ }O \)



Desde ya muchas gracias.

25 Abril, 2011, 07:48 pm
Respuesta #1

gonchi1207

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 29
  • Karma: +0/-0
  • Sexo: Masculino
Por favor, ¿alguien puede contestar?

Gracias.

26 Abril, 2011, 12:08 am
Respuesta #2

gonchi1207

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 29
  • Karma: +0/-0
  • Sexo: Masculino

27 Abril, 2011, 08:00 am
Respuesta #3

gonchi1207

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 29
  • Karma: +0/-0
  • Sexo: Masculino
Nadie ??? No encuentro nada en google una explicacion acerca de este tema.

Ayuda!!!


Gracias.

30 Abril, 2011, 09:07 am
Respuesta #4

gonchi1207

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 29
  • Karma: +0/-0
  • Sexo: Masculino
bue, me mate poniendo los tildes al pedo..... no pasa ná!

01 Mayo, 2011, 03:07 pm
Respuesta #5

Óscar Matzerath

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

Pues es justo lo que te pone en la definición que te han dado. la función \( F: \mathbb{N} \longrightarrow B \) se dice que está definida por recursión primitiva (sin parámetros en tu caso) a partir del elemento \( f_0 \in B \) y de la función \( f_s: \mathbb{N} \times B \longrightarrow B \) si f cumple lo siguiente:

\( F(0) = f_0 \)
\( F(S(n)) = f_s(n,F(n)) \)

Hay un teorema (el que te dan) que dice que dados \( cualquier \) elemento \( f_0 \) y función \( f_s \), existe una única F que definida por recursión primitiva a partir de ellos. Así que el elemento y la función pueden ser las que quieras.
¿Cuál es el sentido de esto? Pues esto te dice que para definir una función en los naturales es suficiente con dar su comportamiento para el 0, y para n>0 una regla que te permita deducir el valor de la función en n a partir de su valor en n-1.

Un ejemplo sencillo: imagínate que quieres definir la función \( exp_2: \mathbb{N} \longrightarrow \mathbb{N} \) dada por \( exp_2(0)=1 \) y \( exp_2(n) = 2^{2^{...^2}} \) donde hay n doses. Así \( exp_2(1)=2 \), \( exp_2(2)=2^2=4 \), \( exp_2(3)=2^{2^2}=16 \), etc. Si quieres ser muy formal, verás que es muy difícil dar una fórmula (por ejemplo en el lenguaje de la aritmética con suma producto y exponenciación) que te defina esta función. Ahora bien, si tomas \( f_0=1 \) y \( f_s: \mathbb{N} \longrightarrow \mathbb{N} \) definida por \( f_s(n)=2^n \), que es muy fácil de definir si tienes exponenciación, el teorema te dice que existe una función definida a partir de esto por recursión primitiva, y es fácil ver que esa función es justamente \( exp_2 \). Así que sabemos que \( exp_2 \) es una función que existe, y tiene sentido definirla.

Sobre la demostración del teorema, la encontrarás en cualquier libro decente sobre teoría de conjuntos. Básicamente la unicidad es muy sencilla por inducción (si dos funciones coinciden en el cero, y suponiendo que coinciden en n también coinciden en S(n), por inducción se concluye que son la misma función). La existencia se basa en considerar aproximaciones (funciones definidas como F pero como dominio un segmento inicial de \( \mathbb{N} \) en vez de todo \( \mathbb{N} \)), ver que una tal aproximación siempre se puede extender, ver que dos aproximaciones son compatibles, y tomar F como la unión de todas las aproximaciones; esto es más complicado, para ver los detalles mírate algún libro.

Sobre lo del esquema de recursión primitiva de un conjunto, sería bueno que nos dieras la definición que te han dado para poder saber a qué te refieres exactamente. De todas maneras, para el primero, tomando \( f_0=0 \) y \( f_s(n)=n+3 \), obtienes una función F que tiene como rango exactamente tu conjunto I (quizás te refieras a esto, pero pon la definición).

Por último comentar que la recursión primitiva es muy importante en la llamada teoría de la recursión o teoría de la computabilidad, ya que las funciones de naturales que se pueden computar mediante un algoritmo (por ejemplo que puedes programar un programa de ordenador que entrando n te de como salida F(n)) son exactamente aquellas que se pueden obtener a partir de unas funciones muy simples (funciones iniciales) a partir de una forma generalizada de composición, recursión primitiva y minimización (total).

Saludos