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.

Fundamentos de las matemáticas:Tras el Santo Grial de las matemáticas

Tras el Santo Grial de las matemáticas es el tercer capítulo del libro Rompiendo códigos. Vida y legado de Turing. Fundamentalmente, en este capítulo del libro, se plantea y desarrolla los principales fundamentos de las matemáticas. Y, en segundo plano, se menciona el curso sobre los fundamentos de las matemáticas impartido por Max Newman en el que participó Alan Turing.

Respecto a la primera cuestión. Durante la segunda mitad del siglo XIX y la primera del siglo XX, los fundamentos de las matemáticas entraron en crisis. Las matemáticas son la ciencia básica por excelencia. Los fundamentos de las matemáticas deben ser sólidos para validar el conocimiento matemático. Por otro lado, el razonamiento matemático está basado en la lógica, y, el método científico se fundamenta en la existencia de axiomas- verdades incuestionables- a través de las cuales se puede deducir el resto de verdades matemáticas- por ejemplo- (los teoremas). De ahí, la importancia de que los fundamentos de las matemáticas sean sólidos "por lo que una de las grandes preocupaciones de las matemáticas ha sido el asegurarse de trabajar sobre cimientos bien establecidos." La lógica matemática ha tenido a matemáticas ilustres como Georg Cantor, George Boole y Gottlob Frege imprescindibles para comprender las matemáticas del siglo XIX y principios del siglo XX. Georg Cantor(1845- 1918) fue un matemático alemán que puso las bases de la teoría de conjuntos en relación con la lógica. Formalizó la noción de infinito. George Boole(1815-1864) fue un matemático inglés que transformó las proposiciones lógicas a ecuaciones matemáticas. Friedrich Ludwig Gottlob Frege(1848-1925) llevó un paso más adelante las ideas de Boole. Sentó las bases de la lógica matemática moderna. Escribió diferentes libros sobre los fundamentos de la aritmética. En 1893, cuando estaba escribiendo un segundo libro sobre los fundamentos de las matemáticas, recibió una carta de Bertrand Russell que le planteó una paradoja. En aquella carta, Bertrand Russell plantea una pregunta: "¿el conjunto de los conjuntos que no forman parte de sí mismos forma parte de sí mismo?" La respuesta a esta pregunta originaba una paradoja: "si no forma parte de sí mismo, pertenece al tipo de conjuntos que no forman parte de sí mosmos y, por lo tanto, forma parte de sí mismo. Y si forma parte de sí mismo, entonces no es un conjunto que no forma parte de sí mismo, así que no puede formar parte." En conclusión, sólo formará parte de sí mismo si no forma parte de sí mismo. Esta paradoja echaba por tierra los fundamentos de la argumentación de Frege. Más tarde, Bertrand Russell logró burlar la paradoja en su obra Principia Mathematica sobre los fundamentos de las matemáticas. Otra aportación fundamental para las matemáticas fue la del matemático David Hilbert. Impartió una conferencia en el Congreso Internacional de Matemáticas en 1900. En ella anunció los 23 problemas más importantes para las matemáticas en el siglo XX. En la lista figuraban estos dos problemas: 1. "Problema de Cantor sobre el cardinal del continuo. ¿Cuál es el cardinal del continuo? 2. "La compatibilidad de los axiomas de la aritmética. ¿Son compatibles los axiomas de la aritmética?" En 1920, David Hilbert lanzó el Programa de Hilbert "que pretendía formar un conjunto de axiomas finito y completo de la aritmética y probar que eran consistentes." Con ello quedaba demostrado la consistencia de las matemáticas. Así, confiaba superar las paradojas como la de Russell. Pero, Kurt Gödel echó por tierra su trabajo. Gödel probó que un sistema axiomático, si el sistema es consistente no puede ser completo. Además, la consistencia de los axiomas no puede ser probada dentro del sistema.

Respecto a la segunda cuestión. En 1935, Alan Turing participó en la Universidad de Cambridge en un curso avanzado sobre los fundamentos de las matemáticas impartido por Max Newman. El curso estaba basado en el trabajo de David Hilbert. En su obra se planteaba tres cuestiones:
1- ¿Son completas las matemáticas?
2- ¿Son consistentes las matemáticas?
3- ¿Son computables?
El seminario de Max Newman concluía con una demostración del Teorema de Incompletitud de Kurt Gödel, "que afirmaba que la propia aritmética era incompleta y que su consistencia no podía probarse dentro de su propio marco axiomático." Este seminario sería un punto de inflexión para el desarrollo de las ideas de Alan Turing.

Alan Turing en Cambridge.

La libertad en Oxford es el segundo capítulo del libro Rompiendo códigos.Vida y legado de Turing. En este segundo capítulo, se centra en la estancia de Alan Turing en la Universidad de Cambridge. 

En 1931, entró en el King's College de la Universidad de Cambridge para estudiar matemáticas. El King's College era un foco del pensamiento liberal en el Reino Unido. Alan Turing mostraba interés por el deporte, especialmente por el remo, de hecho participó en las famosas regatas que enfrentaban a las Universidades de Oxford y de Cambridge. Tuvo amistades tanto de deportistas como de intelectuales. Leyó la Introducción a la filosofía matemática de Bertrand Russell y el libro de John von Neumann de mecánica cuántica. En esta época, se publica su primer artículo "Equivalence of Left and Right Almost Periodicity" en el Journal of the London Mathematical Society(1935). Ese mismo año, leyó su tesis doctoral "On the Gaussion Error Function" con 23 años. En 1936, un año después, ganó el Premio Smith, reconocimiento que la Universidad de Cambridge concede cada año a dos estudiantes en física teórica, matemática aplicada. En esta primera etapa en Cambridge, Turing pasó inadvertido para la mayoría de sus compañeros y profesores, cuando vuelve de su estancia en Princeton, su actitud cambió y se mostró mucho más activo. Muestra de ello, la participación en el curso de Ludwig Wittgenstein, en 1939 en la Universidad de Cambridge, con el que mantuvo varias polémicas entorno a las relaciones entre las matemáticas y el lenguaje ordinario.

Infancia y juventud de Alan Turing.

Infancia y juventud es el primer capítulo del libro: Rompiendo códigos. Vida y legado de Turing.

En este primer capítulo, reseña los aspectos biográficos más remarcables de la infancia y juventud del brillante matemático Alan Turing.

La mayoría de los datos biográficos de la infancia y adolescencia de Alan Turing las proporciona la biografía que escribió su madre en 1955 y que se reeditó en 2012 con motivo del centenario del nacimiento de Alan Turing. Alan Mathison Turing- su nombre completo- nació en 1912 en Paddington, Inglaterra. Su padre, Julius Mathison Turing, trabajaba en el Indian Civil Service, el cuerpo de funcionarios británicos que administraba la India. Alan Turing fue concebido en la India pero nació en Inglaterra. Alan Tuirng "mostró en su infancia ciertas singularidades": hablaba con mucha precisión y cuando aprendió a leer lo hizo en un tiempo récord, de tres semanas. A los seis años, ingresó en la escuela de Hazlehurst. Le consideraban un estudiante superior a la media. Era un niño  que le gustaba desarrollar sus propias ideas. Mostraba un carácter independiente. En 1926, entró en la Sherbone School después de superar el examen de ingreso. Alan Turing no encajaba muy bien en Sherborne School. Era una institución conservadora y estricta. Turing estudiaba por su cuenta matemáticas avanzadas también las novedades de la física como la teoría de la relatividad de Einstein o la mecánica cuántica de Max Planck. El paso por el Sheborne School puede calificarse como "el de un alumno desorganizado, anárquico, incumplidor de las reglas, pero en el que todo el mundo ya veía al genio." Durante sus años en el Sherborne school, entabló amistad con un chico llamado Christopher Morcom, que estaba en un curso superior. Por desgracia, la muerte de Christopher por tuberculosis truncó esa amistad y causó un fuerte impacto en Alan Turing.

Introducción a Rompiendo códigos. Vida y legado de Turing

Vamos a realizar una breve introducción al libro Rompiendo códigos. Vida y legado de Turing de los autores Manuel de León y Ágata Timón. 

Con la introducción, se pretende "trazar la vida del matemático británico Alan Mathison Turing" y "repasar sus logros más importantes." ¿Quién fue Alan Mathison Turing? ¿Cuáles fueron sus contribuciones a la ciencia? Más conocido como Alan Turing fue uno de los grandes matemáticos del siglo XX. Un "hombre del renacimiento" que se interesaba por todo lo que le rodeaba, "cambiando de temas y disciplinas con frecuencia." Fue un personaje decisivo en la Segunda Guerra Mundial, gracias a su trabajo como criptógrafo que aceleró el final del conflicto, al vulnerar las comunicaciones alemanas rompiendo los códigos de las máquinas Enigma, dando un golpe decisivo al exército nazi. De ahí, el nombre del libro: Rompiendo códigos. Vida y legado de Turing. Además, de su perfil como criptógrafo en la Segunda Guerra Mundial, no debemos olvidarnos de la figura de Alan Turing como genio matemático, sus contribuciones en el ámbito teórico de las matemáticas- el problema de la decibilidad o Entscheldungsproblem- y cómo buscando su solución diseñó la máquina universal de Turing, contribuyendo así, al nacimiento y a la fundamentación de las Ciencias de la Computación, y el desarrollo de aplicaciones en el ámbito práctico de las matemáticas como el desarrollo de los fundamentos de la morfogénesis - hoy en día, biología del desarrollo-. Pero, sin duda, la gran contribución de Alan Turing para la posteridad fue la introducción de los conceptos esenciales de la Inteligencia Artificial, es decir, el diseño de máquinas que piensen así como el famoso Test de Turing.

Descripción de Rompiendo códigos. Vida y legado de Turing.

El libro Rompiendo códigos. Vida y legado de Turing de los autores Manuel de León y Ágata Timón tiene 94 páginas. Está editado en el año 2014 por el CSIC y la editorial Catarata dentro de la colección ¿Qué sabemos de ...? con el número 48. 

El sumario del libro Rompiendo códigos. Vida y legado de Turing contiene:

- Una introducción.

- 11 capítulos:

1. Capítulo 1: Infancia y Juventud.
2. Capítulo 2: La libertad de Oxford.
3. Capítulo 3: Tras el Santo Grial de las matemáticas. 
4. Capítulo 4: La búsqueda de la computabilidad.
5. Capítulo 5: Los años de Princeton.
6. Capítulo 6: Rompiendo los códigos alemanes.
7. Capítulo 7: Construyendo ordenadores.
8. Capítulo 8: ¿Pueden pensar las máquinas?
9. Capítulo 9: La morfogénesis.
10. Capítulo 10: La tragedia.
11. Capítulo 11: El legado de Turing. 
12. Hitos en la vida de Turing.

- Una bibliografía.

Presentación de Rompiendo códigos. Vida y legado de Turing.

Rompiendo códigos. Vida y legado de Turing de Manuel de León y Ágata Timón nos invita a adentrarnos en la vida y en el legado de uno de los matemáticos más celebres y brillantes del siglo XX. Aborda tanto la dimensión biográfica del matemático como sus aportaciones más significativas y trascendentales en diferentes disciplinas científicas como las ciencias de la computación, las matemáticas, la Inteligencia Artificial y la morfogénesis-o biología matemática- presentándolo y exponiéndolo de una forma amena y fácil de comprender para cualquier público.

Rompiendo códigos. Vida y legado de Turing es un libro excelente para introducirse en la vida y en el legado científico de uno de los genios de las matemáticas del siglo XX. El libro traza la vida de Alan Turing, desde la infancia hasta su muerte prematura a los 40 años, así como, su legado intelectual en numerosas disciplinas científicas. Aportaciones fundamentales en las ciencias de la computación- su famosa máquina de Turing-; su colaboración activa en las labores de desencriptación de las comunicaciones nazis, rompiendo los códigos de las máquinas Enigma; sus ideas pioneras  en la elaboración de las bases de la inteligencia artificial, construyendo los primeros ordenadores, y el inicio de sus investigaciones inconclusas sobre la morfogénesis- o biología matemática-.