Mostrando entradas con la etiqueta Computabilidad. Mostrar todas las entradas
Mostrando entradas con la etiqueta Computabilidad. Mostrar todas las entradas

11 de febrero de 2016

Biografía completa de Alan Turing III

En este tercer post sobre la biografía completa de Alan Turing vamos a tratar aspectos biográficos de Alan Turing durante la segundad mitad de los años 30, entre 1934 a 1939.

En 1934, Alan Turing concluyó sus estudios de matemáticas. Al año siguiente obtuvo una beca de dos años del King's College. En 1936, ganó el premio Smith, que otorga la Universidad de Cambridge a jóvenes investigadores en física teórica, matemáticas o matemática aplicada, por su trabajo en teoría de probabilidad. Ese mismo año, escribió un artículo científico decisivo titulado "On computable numbers with an application to the Entscheidungsproblem" en el que hará una de las aportaciones científicas más importantes de su vida: la máquina de Turing. En 1935, Alan Turing asistió a un curso en la Universidad de Cambridge. El curso lo impartía el matemático Max Newman cuya especialidad era la topología, una especialidad de las matemáticas, que estudia "las propiedades de los objetos que se conservan cuando los transformamos de manera continua." Ambos trabaron una duradera amistad que se prolongó más allá del fin de la contienda de la Segunda Guerra Mundial.

En agosto de 1936, Alan Turing envía su artículo "On numbers with an application to the Entscheidungsproblem" a la revista Proceedings of the London Mathematical Society. En el artículo, introdujo su célebre máquina de Turing, define también los conceptos de "computable" y "no computable" e incluye algunas ideas fundamentales. Casualmente, ese mismo año, Alonzo Church publicó en la revista American Journal of Mathematics, un artículo titulado "un problema irresoluble de teoría elemental de números". Ambos matemáticos habían llegado a los mismos resultados, aunque por vías distintas: "Mientras Turing razonaba de manera muy original, considerando la clase de operaciones que de "forma mecánica" podría hacer en el mundo real una persona, por ejemplo, un oficinista que repite una tarea una y otra vez, o una máquina que suma dos números, Church razonaba de una forma clásica, dentro del mundo abstracto que es propio de los matemáticos." Alan Turing publicó sus resultados poco después que Alonzo Church los publicará, lo que le restó originalidad al tener que hacer referencia al trabajo de Alonzo Church. Estos dos artículos hoy representan las bases teóricas de la informática.

Alan Turing y Alonzo Church

En septiembre de 1936, Alan Turing viaja a Estados Unidos para realizar sus estudios de doctorado durante 2 años en el Instituto de Estudios Avanzados de la Universidad de Princeton. Alonzo Church sería el supervisor de su tesis doctoral. Fue durante esta época, cuando Alan Turing comenzó a interesarse por la posibilidad de construir su propia máquina. Fue durante su estancia en la Universidad de Princeton cuando nació su interés por el hardware. Empezó a pensar en el soporte físico de la máquina, una época en la que todavía no había ordenadores. En 1938, John von Neumann le ofrece un puesto temporal en la Universidad de Princeton. Sin embargo, Alan Turing rechazó la oferta de John von Neumann. Ese mismo verano regresó al King's College. Una vez allí, comenzó a trabajar sobre un "mecanismo analógico" para confirmar la llamada hipótesis de Riemann. En agosto de 1939, Alan Turing recibe la proposición de incorporarse al Bletchley Park en calidad de criptógrafo para descifrar los mensajes interceptores a los nazis.

Alan Turing en Princeton

17 de enero de 2016

La búsqueda de la computabilidad y la formulación de la máquina de Turing

La búsqueda de la computabilidad es el cuarto capítulo del libro Rompiendo los códigos.Vida y legado de Turing. En este capítulo, se plantea, por un lado, el problema de la decibilidad o Entscheidungsproblem, y, por el otro lado, qué es y cómo funciona una máquina de Turing.

Los fundamentos de las matemáticas, que hemos expuesto anteriormente, son el "contexto histórico" en el que Alan Turing se mueve antes de participar en el curso de Max Newman sobre los fundamentos de las matemáticas. Es en el tercer punto: "¿Son computables las matemáticas?" "¿se pueden diseñar un procedimiento mecánico que, partiendo de una proposición, tras un número finito de pasos, de la conclusión de si es cierta o falsa?" donde se centraran los esfuerzos de Alan Turing. Es el llamado Entscheidungsproblem, es decir, el problema de la decisión. La cuestión fundamental del Entscheidungsproblem es: ¿podemos encontrar ese algoritmo? En la época de Turing no existía una definición precisa de algoritmo. No obstante, fue un aliciente para el propio Turing. Inmediatamente, se puso a trabajar y en 1937 se publicó un artículo transcendental para las ciencias de la computación: "On Computable Numbers, with an application to the Entscheidungsproblem." En el artículo, Turing introdujó varios conceptos: números computables, máquina computadora y máquina universal. Prueba con todo ello que el problema de decisión es insoluble. Turing "reformuló los resultados de Kurt Gödel de 1931, reemplazando el lenguaje formal basado en la aritmética de Gödel por el concepto de máquina de Turing." ¿Cómo funcionaba la máquina de Turing? "Este instrumento abstracto funciona moviéndose de un estado a otro, siguiendo un número finito de reglas concretas. Puede escribir un símbolo en la cinta o borrarla. Así, una máquina de Turing sería capaz de realizar cualquier computación matemática si esta se representa como un algoritmo." De esta manera, Turing pudo demostrar que no hay solución al Entscheidungsproblem. Concluyó a su vez que el problema de la parada es indecidible, es decir, que no es posible decidir algorítmicamente si una máquina de Turing se detendrá o no. Por otro lado, Turing describe conceptualmente qué es una máquina universal de Turing como la de un ordenador "donde la cinta desempeñaba el papel del programa en los ordenadores modernos." Y definió qué era un número computable "como un número real cuya expresión decimal podía ser producida por una máquina de Turing." También describió un número que no es computable. Dejó claro que la mayoría de los números reales no son computables.

¿Qué era realmente una máquina de Turing? Una máquina de Turing es un dispositivo abstracto, no físico. Está constituida por una serie de elementos: una cinta infinita, dividida en casillas, un dispositivo móbil, que cuenta a su vez con un cabezal que puede leer o borrar el símbolo que está impreso en la cinta. Existe además un registro capaz de almacenar un estado determinado, que viene definido a su vez por un símbolo. Los símbolos que definen el estado del dispositivo no tienen por qué coincidir con los símbolos que se pueden leer o escribir en la cinta. ¿Cómo funciona? La máquina de Turing funciona de forma mecánica y secuencial: "Primero lee el símbolo que hay en la casilla que tiene debajo. Después toma el símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la cual, siguiendo las instrucciones, lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha." La ejecución de una máquina de Turing seguiría indefinidamente, al menos que se detenga. Esto supondría que llega a una estado en el que se detiene, permitiendo examinar la cinta para buscar el resultado. Una máquina de Turing puede utilizarse para todo tipo de operaciones matemáticas. Es posible programarla para que simule el comportamiento de un ordenador. Cualquier máquina de Turing puede ser codificada en cualquier computador "por pequeño que sea, sería posible emular en nuestro procesador una máquina de Turing que simule un superordenador." Ésta es la idea de la máquina universal de Turing, es decir, una máquina capaz de imitar el comportamiento de cualquier otra máquina con independencia del algoritmo para el que haya sido diseñada.

máquina universal de Turing