Función recursiva

Función recursiva

En lógica matemática y computación, 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 (estas se obtienen por medio de recursión primitiva y composición de funciones iniciales). No toda función recursiva es primitiva recursiva. El ejemplo más conocido es la función de Ackermann.

Existen otros sistemas formales equivalentes en cuanto a poder de expresión, por ejemplo el Cálculo Lambda y las cadenas de Markov.

Definición

Para definir las funciones recursivas se toma la definición de las funciones primitivas recursivas, para permitir funciones parciales, agregando el operador de búsqueda o minimización no acotada como sigue:

Si f(x,z1,z2,...,zn) es una función parcial sobre los naturales con n+1 argumentos x, z1,...,zn, la función μx f es la función parcial con argumentos z1,...,zn que retorna el más pequeño x tal que f(0,z1,z2,...,zn), f(1,z1,z2,...,zn), ..., f(x,z1,z2,...,zn) están todas definidas y f(x,z1,z2,...,zn) = 0, si un tal x existe; en caso contrario, μx f no está definida para los valores particulares de los argumentos z1,...,zn.

Se puede verificar que la especificación del mínimo valor de x, junto con el resto de la definición idéntica a la de las funciones primitivas recursivas, implican el axioma de búsqueda acotada de las funciones primitivas recursivas.

El conjunto de las funciones recursivas parciales está definido como el más pequeño conjunto de funciones parciales con cualquier número de argumentos de los naturales en los naturales que contiene el cero, el sucesor y las funciones de proyección, tales que la composición, la recursión primitiva y la búsqueda no acotada son operaciones cerradas en este conjunto.

El conjunto de las funciones recursivas totales es el subconjunto de las funciones recursivas parciales que además son funciones totales.

En la tesis de Church-Turing se establece el paralelo entre máquinas de Turing que no se detienen para ciertas entradas y el resultado indefinido de una función recursiva parcial. El operador de búsqueda no acotada no puede ser definido usando las reglas de definición de las funciones primitivas recursivas, dado que no se dispone en ellas de un mecanismo de iteración no acotada por el cual podría no encontrarse el resultado de una función.


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Función recursiva — En lógica matemática y computación, 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… …   Enciclopedia Universal

  • Función de Ackermann — En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue …   Wikipedia Español

  • Función — (Del lat. functio, onis.) ► sustantivo femenino 1 BIOLOGÍA Actividad o capacidad de acción específica de un ser vivo y de sus órganos: ■ la función del riñón; la función clorofílica. 2 Desempeño de un cargo u oficio: ■ el vicepresidente desempeña …   Enciclopedia Universal

  • Función beta de Gödel — En lógica matemática, la función beta de Gödel es una función numérica que permite la definición de funciones recursivas dentro de una teoría formal aritmética. Definición y propiedades La definición de la función beta es la siguiente: Dados tres …   Wikipedia Español

  • Función de Ackermann — La función de Ackermann, utilizada en la teoría de la computación, es una función recursiva que toma dos números naturales como argumentos y devuelve un número natural …   Enciclopedia Universal

  • Recursión primitiva — Saltar a navegación, búsqueda En Teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad. Se definen usando como principales… …   Wikipedia Español

  • Cálculo lambda — Artículo parcialmente traducido: Contiene texto en inglés. Ayuda a terminarlo. El cálculo lambda es un sistema formal diseñado para investigar la definición de función, la noción de aplicación de funciones y la recursión. Fue introducido por… …   Wikipedia Español

  • Teoremas de incompletitud de Gödel — Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1930. Ambos están relacionados con la… …   Wikipedia Español

  • Teorema de Laplace — El teorema de Laplace (también conocido como regla de Laplace o desarrollo de Laplace), así llamado en honor del matemático francés homónimo es un teorema matemático que permite simplificar el cálculo de determinantes en matrices de elevadas… …   Wikipedia Español

  • Haskell — Información general Paradigma Funcional, no estricto, modular, fuertemente tipificado Apareció en 1990 Diseñado por Universidad de Yale, Universidad de Glasgow …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”