Mostrando entradas con la etiqueta Cálculo lambda. Mostrar todas las entradas
Mostrando entradas con la etiqueta Cálculo lambda. Mostrar todas las entradas

19 de enero de 2016

Los años de Princeton: la relación de Alan Turing con Alonzo Church.

Los años de Princeton es el quinto capítulo del libro Rompiendo código. Vida y legado de Turing. Básicamente se centra en la estancia de Alan Turing en Princeton, su relación con el matemático Alonzo Church y la elaboración de su tesis doctoral.

En 1936, Alan Turing entregó el manuscrito del famoso "On Computable Numbers, with an application to the Entscheidungsproblem" al físico John von Newmann. En mayo de ese mismo año, recibió una copia del artículo del matemático Alonzo Church, titulado "An unsolvable problem in elementary number theory", que había sido publicado en la revista American Journal of Mathemarics, y que probaba, aunque con una aproximación diferente, las ideas de Turing sobre la problemática de la indecibilidad, es decir, la imposibilidad de decidir si una máquina de Turing se detendrá o no a través de algún tipo de algoritmo. Alonzo Church introducía en el artículo el concepto de "lambda- definibilidad" que equivalía al de computabilidad de Alan Turing. Church utilizaba el cálculo lambda para demostrar la insolubilidad del Entscheidungsproblem. Esta coincidencia generó un problema para que el artículo de Turing pudiera ser publicado en la revista Proceedings of the London Mathematical Society. Pero, finalmente pudo publicarlo cuando introdujo cambios y referencias al artículo Alonzo Church. Newmann animó a Turing a que conociera a Alonzo Church en Princeton. En setiembre de 1936, Turing partió rumbo a EE.UU. Su vida en Princeton era muy diferente a la de Cambridge. Era un ambiente más informal y chocaba con su "carácter inglés". La redacción de su tesis doctoral la inició bajo la supervisión de Alonso Church. La estancia en Princeton era sólo para un año. Princeton le ofreció permanecer un año más, e incluso lo arreglo con el King's College para que así fuera, pero Turing optó finalmente por volver a Cambridge donde siguió con la elaboración de su tesis doctoral. Inició una línea de trabajo entorno a la hipótesis de Riemann.

La hipótesis de Riemann la formuló el matemático alemán Bernhard Riemann a mediados del siglo XIX. Estudió la distribución de los números primos y observó una estrecha relación entre el orden en el que se presentan y la función zeta de Riemann- o función definida sobre los números complejos-. Demostró que probar la hipótesis de Riemann nos daría mucha información sobre los números primos. Hasta la fecha, nadie lo ha conseguido. Turing tampoco pudo avanzar en este tema. De vuelta a Princeton, Turing finalizó su tesis "Systems of logic based on ordinals" en mayo de 1938. En su tesis, introdujo varios conceptos: lógica ordinal y computación relativa. Además de la idea de oráculo que permitía estudiar problemas que no se pueden abordar con una máquina de Turing. Para concluir, la contribución entre ambos, Alan Turing y Alonzo Church, fue en las dos direcciones: "por un lado, Church ayudó a Turing a mejorar algunos aspectos que eran deficientes en su planteamiento, pero también Turing contribuyó a hacer más accesibles los resultados de Church." Un discípulo de Alonzo Church, Stephen Kleene propuso la llamada Tesis de Church- Turing, que, suponiendo una capacidad de almacenamiento ilimitada, establece que la capacidad potencial de cómputo de cualquier ordenador es similar, pero no su velocidad de cálculo que puede variar.

Alonzo Church