calculo labda

CALCULO LAMBDA “λ”
1. INTRODUCCION: El Cálculo Lambda es el más pequeño lenguaje universal de programación, consiste en una regla de transformación simple “sustituir variables” y un esquema simple para definir funciones.
El cálculo lambda se puede decir que es equivalente a las máquinas Turing porque es capaz de evaluar y expresar cualquier función computable. Church había querido hacer unsistema formal completo para modelizar la matemática pero después separó el cálculo lambda y lo ideó para que estudiara la computabilidad.
El cálculo lambda permite estudiar las propiedades de las funciones, de tal forma que se constituye en la teoría que formaliza los lenguajes funcionales, facilitando la rigurosa evaluación y prueba de expresiones. La forma elemental de ver el cálculo lambdapuro es: Ax.M que constituyen las llamadas abstracciones, donde x es el parámetro de la función y M el cuerpo.
2. HISTORIA: El cálculo lambda fue introducido por el matemático Alonzo Church en la década de 1930 como parte de una investigación sobre los fundamentos de las matemáticas. El sistema original ha demostrado ser lógicamente inconsistente en 1935 cuando Stephen Kleene y JB Rosserdesarrollaron la paradoja Kleene-Rosser.

Posteriormente, en 1936 publicó Iglesia aislada y sólo la parte correspondiente a la computación, lo que ahora se llama el cálculo lambda sin tipo. En 1940, se introdujo también un sistema de cómputo más débil, pero lógicamente consistente, conocido como el cálculo lambda simplemente mecanografiado.
Church usó el cálculo lambda en 1936 para resolver elEntscheidungsproblem, con la cual probó que no había algoritmo que pudiese ser considerado como una "solución"
al Entscheidungsproblem.

Independientemente el mismo año, Turing prueba lo mismo con su “Máquina de Turing”.
David Hilbert, siguiendo con su programa con el cual propone desafíos a los matemáticos “23 Problemas de Hilbert del 1900”, formula 3 preguntas en 1928, la tercera de las cuales seconoce como:
“Hilbert's Entscheidungsproblem”.

El Entscheidungsproblem: es el reto en lógica simbólica de encontrar un algoritmo general que decida si una fórmula del cálculo de primer orden es lógicamente válida.
El teorema de completitud de Gödel, postula que una formula lógica es lógicamente válida si y solo sí, para cada interpretación, la misma es verdadera.

El calculo lambda fuedesarrollado también como una teorìa que provee reglas para manipular funciones en una manera puramente sintàctica. Ha tenido
enorme influencia en los siguientes campos:
• Lògica Matemàtica.
• Teorìa de la Computabilidad.
• Semántica Formal “Denotacional” de los lenguajes de programación.
• Programación Funcional: todos los lenguajes funcionales pueden ser vistos como variaciones
sintácticas delCálculo Lambda. Además, sus semánticas y sus implementaciones
pueden ser analizadas en el contexto del Cálculo Lambda.
Para introducir la notación básica, revisemos el concepto de función. Una función es
una correspondencia entre elementos del dominio y elementos del codominio especificada
por medio de una o varias reglas tal que a cada elemento del dominio le corresponde cuando
más un únicoelemento del codominio. Por ejemplo:
cubo : Entero ! Entero donde cubo(n) = n³
Una definición como esta puede llevar a las siguientes preguntas:
• ¿Cuál es el valor del identificador cubo?
• ¿Cómo podemos representar el objeto ligado a cubo?
• ¿Puede esta función ser definida sin darle un nombre?
Comencemos por este ultimo. La notación λ ¸ de Church permite la definición de funcionesanónimas, es decir, funciones sin nombres asociados:
λn . n³ define la función que asocia a cada n en el dominio con n³
Diremos que la expresión representada por λn . n³ es el valor ligado con el identificador
cubo.
El número y orden de los parámetros de la función son especificados entre el símbolo λ
y una expresión. No hay ambigüedad porque se especifica el orden de los parámetros:
λn . λm . n...