Angel "Java" Lopez en Blog

Publicado el 14 de Abril, 2009, 17:50

Desde el renacimiento de la cultura en Europa (luego de una Edad Media que también tuvo lo suyo), las matemáticas lograron colocarse a la altura de los antiguos griegos, y superarlos. Por un lado, la aparición del análisis, por el otro, el álgebra de ecuaciones, avances en teoría de números, y el florecimiento de ideas, notaciones (como el plano cartesiano, la notación para números completos), hicieron que el desarrollo matemático alcanzara nuevas alturas. Genios como Newton, Laplace, Fermat, Lagrange, Fourier, Gauss, Euler, Galois, Abel, Cauchy (para nombrar sólo a unos pocos) todavía dieron más impulso a toda esta cosecha de éxitos. Pero mientras que el análisis crecía, ocupándose de problemas cada vez más complejos, acumulando resultados, el fundamento de todo esto (desde el paso al límite como problemas de existencia de soluciones) no fue tratado con el debido detalle. Igual, todo avanzaba, así que el problema de los fundamentos, no era problema.

Pero en el siglo XIX, con la aparición de las geometrías no euclideanas, y algunos temas en análisis (curvas teratológicas, sin derivadas), el tema de los fundamentos de lo que se estaba haciendo, apareció en el ambiente matemático. Para hechar más leña al fuego, surgieron las novedades en lógica de parte de Boole, la aparición de los conjuntos con Cantor (y el estudio de los problemas del infinito). Aun cuando Frege hiciera todo lo posible para fundar su trabajo en una teoría de conjuntos, el bueno de Bertrand Russell le destruyó sus bases, encontrando su famosa paradoja, derivada del conjunto de todos los conjuntos que no se incluyen a sí mismos.

El replanteo de la geometría, el nacimiento de la topología, las ideas de Riemann sobre variedades, la búsqueda del formalismo por Hilbert, la justificación de los reales, pases al límite, convergencia de series, todo llevó a que los fundamentos de las matemáticas pasaran a estar en el primer plano de la actividad de entonces.

Ya llegados al siglo XX, el trabajo de Gödel, Turing y otros llevó a tratar de buscar otras formas de fundamentar ramas de las matemáticas. Uno de los intentos, que tendría influencia más adelante en las ciencias de la computación, fue el trabajo de Church sobre su cálculo lambda.

¿Qué es una función? Hoy pensamos una función como un grafo, algo que asigna a puntos de un dominio, otros puntos de un codominio. Pero al principio del siglo XX, la función se veía como una fórmula, para, digamos, dado uno o varios parámetros, obtener un resultado. El cálculo lambda es una teoría de funciones tomadas como fórmulas, y al describir el resultado de una función en base a una descripción del cálculo a realizar, tiene puntos de contacto con lo que luego surgió como ciencia de la computación.

Pero volvamos a principios del siglo XX. La teoría de conjuntos había brindado una base a los lógicos para tratar sus paradojas. Por otro lado, los matemáticos se vieron más inclinados a seguir por el camino del estudio de las estructuras (de la mano de Bourbaki), y luego, en la teoría de las categorías.

Pero tanto conjuntos, estructuras como categorías, no tratan directamente de algoritmos, sobre cómo una función opera sobre sus argumentos. Como otra forma de fundar algunas partes básicas de las matemáticas, Alonzo Church propone el cálculo lambda en 1933.

Su idea es explorar una alternativa a los fundamentos de las matemáticas. En lugar de basarse en conjuntos como Cantor y Frege, pone al concepto de función en el centro, de esta manera:

- Una función corresponde a un conjunto
- Un argumento de una función corresponde a un elemento del conjunto
- La aplicación de una función a su argumento corresponde a la pertenencia del elemento al conjunto
- La definición de una función por sus valores, corresponde a la definición de un conjunto mediante alguna propiedad de sus elementos. 

Así se pasa de la teoría ingenua de conjuntos (que no está advertida de las paradojas) a una teoría ingenua de las funciones. Por un lado, tenemos el principio de extensión: una función está determinada completamente por sus valores, y dos funciones son iguales si, ante los mismos argumentos, arrojan los mismos resultados. Y por otra, el principio de comprensión: cada descripción de los valores, da una función, y cada función se determina por la descripción de los valores (podríamos ver al descripción como el algoritmo para pasar de los argumentos al resultado).

Church no fue el único que desarrolló el cálculo lambda. Tuvo el auxilio principal de su alumno, Kleene. Juntos, pudieron describir, en cálculo lambda, funciones lógicas como Y, O, y también describieron números, y el concepto de sucesor de número, a lo Peano. Curiosamente, por un tiempo, pensaron que era imposible describir en cálculo lambda, a la función predecesor de un número, pero luego Kleene encuentra una respuesta. Como en ese momento a Kleene le estaba saliendo una muela del juicio, la función predecesor descubierta se denomina a veces "el truco de la muela del juicio".

Con el tiempo se vió y demostró, que el cálculo lambda era equivalente a:

- La máquina de Turing
- Las funciones recursivas generales de Gödel 

De alguna forma, el definir una función f(x) en cálculo lambda, era responder si era computable o no, en términos de Turing.

Notablemente, en cálculo lambda, "todo" son funciones, hasta los argumentos.

Recordemos que la paradoja de Russell se basaba en el conjunto de todos los conjuntos que no pertenecían a sí mismos. En el caso del cálculo lambda, se trata de considerar las funciones a las que se les pasa como argumento la misma función. Y acá debería entrar en demasiados detalles técnicos (para una detallada descripción, ver los enlaces que enumero al final), pero resulta que no aparecen paradojas.

Finalmente, un teorema de Church y Rosser demostró que el cálculo lambda era una teoría algo singular: por un lado, se basaba en principios ingenuos, no sofisticados, no armados de antemano para evitar las paradojas, pero demostrablemente consistente, y al reparo de las paradojas actuales y potenciales. Pero el precio a pagar fue que la teoría no permitió definir la negación, y se abandonó el abarcar toda la lógica. Así que se abandonó al cálculo lambda como fundamento para toda la matemática.

Pero en 1936, como comentaba antes, Church y Kleene consiguen englobar la aritmética. Lo que se sabe hoy, es que se puede reprensentar en cálculo lambda todas las funciones que se pueden describir en los lenguajes comunes de programación universal. Claro que Church y Kleene consiguieron este resultado notable antes de la aparición de los computadores, como Turing.

Hay un teorema de punto fijo, que dice que toda función f en cálculo lambda tiene un punto fijo, un x tal que f(x) = x da el propio argumento. Esto dió la base a los programas autorreferenciales o recursivos, actualmente de uso común en la programación. En tiempos más modernos, Dana Scott (1969) propone la semántica denotacional para el cálculo lambda, desarrollando técnicas que permiten tratar a los programas de computación como objetos de naturaleza matemática, pasando la computación, de alguna forma, a ser una rama de las matemáticas modernas. Por ese trabajo, Scott recibió en 1976 el Turing Award, algo así como el premio Nobel de informática.

(No, lamento desilusionarlos, no me han dado el Turing... aún... ;-) ;-)

En febrero, escribí una implementación de cálcula lambda en

Presenting AjLambda, lambda calculus in C# 

Para aprender más, este es el primer paper a leer:

Lecture Notes on the Lambda Calculus (pdf) (excellent paper to learn Lambda Calculus)

Más info en

Lambda calculus - Wikipedia, the free encyclopedia

A Tutorial Introduction to the Lambda Calculus

Ayer me enteré de esto:

Dana Scott Receives Gold Medal for Contributions to Mathematics

Nos leemos!

Angel "Java" Lopez
http://www.ajlopez.com/
http://twitter.com/ajlopez