Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Funciones Recursivas

Computabilidad, Fundamentos de la teoría de funciones recursivas, Alcance de las funciones recursivas primitivas, Poder de los lenguajes de programación, Funciones recursivas parciales. Hecho por Elmer Zambrano.
by

Arianna Peralta

on 1 August 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Funciones Recursivas

Funciones Recursivas
Computabilidad
También llamada teoría de la repetición, es una rama de la lógica matemática, de la informática y de la teoría de la computación que se originó en la década de 1930 con el estudio de las funciones computables y los grados de Turing. El campo ha crecido desde entonces para incluir el estudio de la computabilidad generalizada y definibilidad. En estas áreas, la recursividad se solapa con la teoría de la teoría de la prueba y la teoría de conjuntos descriptiva eficaz.
Alcance de las funciones recursivas primitivas
Se inicia el estudio de las funciones recursivas primitivas considerando la colección de las funciones constantes, las cuales producen una salida predeterminada, sin importar cuál sea la entrada. Las funciones constantes cuyas salidas son tuplas de un solo elemento están representadas por K a la ‘n’ sub ‘m’, donde n indica la dimensión del dominio y m es el valor de salida de la función. Así, K a la ‘2’ sub ‘3’ establece la correspondencia entre cualquier tupla de dos elementos y el entero 3.
El poder de los lenguajes de programación
Al igual que los idiomas sirven de vehículo de comunicación entre los seres humanos, existen lenguajes que realizan la comunicación entre los seres humanos y las computadoras. Estos lenguajes permiten expresar los programas o el conjunto de instrucciones que el operador humano desea que la computadora ejecute.

¿Qué aspectos deben incluirse para garantizar que, una vez diseñado e implantado un lenguaje de programación, no descubramos que existen problemas cuyas soluciones no pueden especificarse con el lenguaje, y que sí podrían haberlo sido si hubiéramos implantado una versión ampliada del lenguaje?
Funciones recursivas parciales
Toda máquina de Turing Z define de manera natural una función F cuyo dominio está formado por todos los enteros positivos n tales que #n es una entrada válida para Z, es decir, todos los números que, cargados en Z dan (después de una cantidad finita de tiempo) una salida que representa un entero positivo. El número F(n) se define entonces del siguiente modo: F(n) = m si y sólo si #m es la salida que corresponde a la entrada #n. Definición: Diremos que una función G es recursiva parcial si existe una máquina de Turing Z tal que la función F por ella definida coincide exactamente con la función G (es decir, si F y G tienen el mismo dominio y además para cada número n de ese dominio vale que F(n) = G(n)). Cuando el dominio de G está formado por todos los enteros positivos, decimos simplemente que la función es recursiva.
Computabilidad de Turing
La principal forma de computabilidad estudiado en la teoría de la recursividad se introdujo por Turing. Un conjunto de números naturales se dice que es un conjunto computable si hay una máquina de Turing que, dado un número n, se detiene con la salida 1 si n está en el conjunto y se detiene con la salida 0 si n no está en el conjunto. Una función f de los números naturales a sí mismos es una función recursiva o computable si hay una máquina de Turing que, en n de entrada, se detiene y devuelve la salida f. El uso de máquinas de Turing aquí no es necesario, hay muchos otros modelos de cálculo que tienen la misma potencia de cálculo como máquinas de Turing, por ejemplo funciones de la-recursivas obtuvieron a partir de recursión primitiva y el operador
La terminología de las funciones recursivas y conjuntos no es completamente uniforme. La definición en términos de funciones recursivas, así como una definición diferente de funciones recursivas por Gödel llevaron a el nombre tradicional recursiva para los conjuntos y funciones computables por una máquina de Turing. La palabra decidible se deriva de la palabra alemana Entscheidungsproblem que se utilizó en los documentos originales de Turing y otros. En uso contemporáneo, el término "función computable" tiene diversas definiciones: de acuerdo con Cutland, que es una función recursiva parcial, mientras que, según SOARE es una función recursiva total.
Computabilidad de Turing
Para que este método pueda llevarse a cabo sin ambigüedades es necesario numerar
los estados a partir del 1, es decir, Q = {q1,...,qn}.
También en este caso definiremos una serie de e.r.(en este caso, de forma recursiva) que inicialmente serán incógnitas que es necesario calcular.

Cada e.r. R^k_ij representara a las cadenas que permiten llegar del estado qi al estado qj
pasando exclusivamente por los estados q1,...,qk. Definiremos R^0_ij como el conjunto de cadenas (en este caso, símbolos) que nos llevaran directamente del estado qi al estado qj. Las e.r del tipo R^0_ij se definen de forma directa, mientras que las e.r. R^k_ij, k ≥ 1 se definen de forma recursiva.
El método de las funciones recursivas
A pesar de que esta definicion es muy intuitiva no es lo suficientemente estricta como para definir los casos mas complejos de recursividad.
Diremos que una funcion recursiva es total si esta definida para todos los valores del conjunto origen y parcial si lo esta solo para un subconjunto propio del conjunto origen.
Para definir un conjunto de manera recursiva se especifican ciertos objetos del conjunto y luego se describen uno o mas metodos generales que permiten obtener nuevos elementos a partir de los existentes.

Por ejemplo, podemos definir recursivamente el lenguaje Σ* ası:
λ E Σ*
Para cada w E Σ* y cada a E Σ tenemos que aw E Σ
Fundamentos de la teoría de funciones recursivas
Fundamentos de la teoría de funciones recursivas
Definición

Una función f : N^n --> N se considera recursiva si tiene los siguientes elementos:

Definiciones básicas que establecen de manera axiomática el valor que toma la función para determinados valores del conjunto origen.
Por ejemplo, f act(0) = 1.

Una o más reglas recursivas que permiten calcular nuevos valores de la función a partir de otros valores conocidos.
Por ejemplo, f act(n) = n×f act(n−1), n ≥ 1

Aplicar las definiciones básicas y las recursivas un número finito de veces debe ser suficiente para calcular cualquier valor de la función.

Funciones Recursivas
Las funciones recursivas o también conocidas como funciones recursivas-μ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo. De hecho, en teoría de la computabilidad se demuestra que las funciones recursivas son precisamente las funciones que pueden ser calculadas con el formalismo de cómputo más general conocido como lo son las máquinas de Turing. Las funciones recursivas están relacionadas con las funciones primitivas recursivas y su definición inductiva se construye basándose en la de las funciones primitivas recursivas.
Las dos ultimas columnas se han calculado mediante la formula recursiva vista anteriormente.

Funciones Recursivas Primitivas
Son recursivas primitivas las funciones constantes cuyas salidas tienen más de una componente, ya que no son más que combinaciones de funciones de la forma K a la ‘n’ sub ‘m’. Por ejemplo, la función que establece la correspondencia entre cualquier tupla de tamaño 3 y el par (2; 5) es K a la ‘3’ sub ‘2’ x K a la ‘3’ sub ‘5’. Para evitar notaciones complicadas, en aquellos casos en los que la dimensión del dominio sea evidente o no tenga importancia para el análisis, representaremos las funciones constantes directamente con su valor de salida, es decir, 3 en lugar de K a la ‘2’ sub ‘3’ o (2; 5) en lugar de K a la ‘3’ sub ‘2’ x K a la ‘3’ sub ‘5’
Utilizando las funciones constantes, podemos mostrar de la manera siguiente que la función producto es también recursiva primitiva:
producto(x; 0) = 0
producto(x; y + 1) = x + producto(x; y)
es decir:
producto(x; 0) = K a la ‘1’ sub ‘0’(x)
producto(x; y + 1) = suma[π a la ‘3’ sub ‘1’ x π a la ‘3’ sub ‘3’ (x; y; producto(x; y))]

De forma similar, podemos mostrar que la función potencia es también recursiva primitiva:
potencia(x; 0) = 1
potencia(x; y + 1) = X*potencia(x; y)
es decir:
potencia(x; 0) = K a la ‘1’ sub ‘1’ (x)
potencia(x; y + 1) = producto(x; potencia(x; y))

Funciones Recursivas Primitivas
La estrategia va a ser desarrollar un sencillo lenguaje de programación esencial que permita, suponiendo verdadera la tesis de Church-Turing, expresar una solución para cualquier problema que puede resolverse de manera algorítmica.

También la palabra programación se define como el proceso de creación de un programa de computadora, mediante la aplicación de procedimientos lógicos, a través de los siguientes pasos:

* El desarrollo lógico del programa para resolver un problema en particular.
* Escritura de la lógica del programa empleando un lenguaje de programación específico (codificación del programa).
* Ensamblaje o compilación del programa hasta convertirlo en lenguaje de máquina. * Prueba y depuración del programa.
* Desarrollo de la documentación.
El poder de los lenguajes de programación
Funciones recursivas parciales
La función G(n) = n – 1 (cuyo dominio está formado por los enteros mayores que 1) es recursiva parcial. Para dar otro ejemplo, veamos que la función H(n) = log n, cuyo dominio es el conjunto de las potencias de 10, es también recursiva parcial. Gracias a la Tesis de Turing no será necesario mostrar explícitamente una máquina T que calcule H(n), alcanzará con mostrar cualquier algoritmo que haga ese cálculo, la Tesis nos garantiza que dicho algoritmo podrá traducirse a una máquina T. En este caso un algoritmo puede describirse de la siguiente manera:
1) Entrada: n.
2) Defina k = 1.
3) Calcule 10 elevado a la k y compárelo con n, si son iguales deténgase, en caso contrario vaya al paso siguiente.
4) Sume 1 al valor de k y vuelva al paso 3).
5) Salida: k.
Muchas gracias por su atención!
Integrantes:
Pedro Amair
Numa Baez
Jaime Marín
Arianna Peralta
Elmer Zambrano
Full transcript