Se acerca el Simposio Internacional de Alan Turing organizado por la Real Academia de Ciencias, que traerá a la Fundación Areces a expertos mundiales en las ramas de la ciencia de las que fue precursor el matemático inglés. Inteligencia Artificial, computación, lógica, criptografía, matemáticas aplicadas a la biología… aun hoy, casi sesenta años después de su muerte, todos estos campos siguen estando tremendamente influidos por el trabajo visionario de Turing.
Durante estas semanas estamos haciendo una breve introducción de algunos de estos temas y de su representación en el congreso, destacando los ponentes que transmitirán la importancia del legado de Turing en sus respectivos campos. Seguimos con sus investigaciones más profundas: los límites del quehacer matemático.
Recordamos que todavía está abierto el periodo de subscripción (gratuita) para el Simposio, que tendrá lugar los días 23 y 24 de octubre. Se puede rellenar el formulario de inscripción en la página web de la Fundación Areces.
Alan Turing no solo fue fundamental en los inicios de la computación, sino que también tuvo un papel protagonista en el estudio de sus límites. En el propio diseño ya observaba que aquello no era infalible.
En 1935 formuló el Teorema de la Parada, que equivale al teorema de Incompletitud de Gödel, pero formulado con máquinas de cómputo.
Según los teoremas de incompletitud de Gödel, en ’cualquier’ teoría matemática hay formulas que aunque intuitivamente parezcan ciertas no son demostrables en el sistema original.
Tras diseñar su famosa Máquina de Turing, consiguió́ demostrar ésta era capaz de realizar casi cualquier cálculo, si se la dejaba trabajar un numero suficiente de pasos y se habían preparado de forma correcta sus estados,
Sin embargo, empezó a plantearse si, efectivamente, podría tratar con cualquier entrada. Llegó a la siguiente pregunta, llamada ‘El problema de la parada’:
Antes de poner la máquina en marcha, ¿se podía determinar mediante un algoritmo si llegaría a un resultado satisfactorio?.
El teorema de la parada
Turing demostró que la respuesta es negativa, es decir, que no siempre es posible hacer esa predicción. Para ello, utilizó la demostración por reducción al absurdo (se prueba que una proposición matemática es verdadera probando que si no lo fuera conduciría a una contradicción).
Manuel Alfonseca (Universidad Autónoma de Madrid) da, en el blog del Año de Turing de El País, una demostración intuitiva del teorema de la parada:
“1. Supongamos que el problema de la parada tiene solución.
2. Entonces, es posible programar una máquina de Turing para resolverlo. Sus datos de entrada serán la descripción de la máquina de la que queremos predecir si se para, y los datos de entrada de esta. La máquina contestará SI (si la otra máquina se va a parar con esos datos) o NO (si no se va a parar con esos datos).
3. Modificamos la construcción de la máquina que resuelve el problema de la parada. En vez de contestar SI, hacemos que se meta en un bucle del que no pueda salir. Cuando tenga que contestar NO, hacemos que se pare. (Este cambio es muy sencillo).
4. Por último, le damos a esta máquina la descripción de ella misma y le preguntamos si se para o no. Con la modificación que hemos hecho, si la máquina se va a parar, en vez de responder SI debe meterse en un bucle, es decir, no se debe parar. Si no va a pararse, debe pararse. Pero esto es una contradicción. Luego la hipótesis inicial es falsa. Luego el problema de la parada no tiene solución.”
Implicaciones
Por tanto no había forma de esquivar los resultados de Gödel. Las matemáticas eran un montaje intelectual y no tenían más trascendencia metafísica que el ajedrez.
En 1938 Turing volvió a explorar el concepto de ‘incomputable’ en su tesis que defendió en Princeton en 1939 con el título ‘Sistemas Lógicos Basados en Ordinales’.
La situación de ‘indecibilidad’ de la matemática incomodaba a Turing y a muchos de sus colegas, y con su teoría de ‘lógicas ordinales’ intentó ‘evitar lo máximo posible los efectos de la Teoría de Gödel’, estudiando el efecto de añadir una proposición verdadera pero formalmente indemostrable de Gödel como axioma para crear lógicas más fuertes. Al final, no llegó a ninguna conclusión definitiva.
En estos trabajos Turing introdujo el concepto de ‘oráculo’, es decir, de una especie de componente mágica que era capaz de realizar operaciones incomputables. Va más allá de cualquier unidad elemental de un ordenador moderno, ya que es infinitamente más potente. Llamó ‘máquinas oráculo’ a aquellas máquinas que incluían esta capacidad y que, por tanto, dejaron de ser puramente mecánicas, ya que, justamente el interés en esta construcción residía en explorar aquello que no se podía realizar con procesos mecánicos.
El oráculo como la intuición matemática
La característica definitoria del oráculo de Turing es que no puede ser una máquina. Puede ser considerado una herramienta matemática, que permite formular preguntas acerca de la computabilidad relativa, más que de la absoluta.
Con ello, abrió nuevas vías de investigación en lógica, pero también tuvo implicaciones en el estudio y el conocimiento de la capacidad cognitiva de los seres humanos.
En una interpretación el oráculo se relaciona con la intuición humana que permite ver la verdad en una proposición indemostrable de Gödel. Es ‘tener una idea’, frente a ‘usar un método mecánico’.
Aun así, el oráculo es demasiado poderoso para ser identificado realmente con ninguna capacidad humana, ya que resuelve operaciones incomputables. La idea dio pie a teorías casi propias de la Ciencia Ficción, como las del matemático Roger Penrose, que llegó a afirmar que la habilidad de la mente para ver verdades indemostrables formalmente muestra que tienen que haber operaciones físicas incomputables en el cerebro.
En el simposio
- “Alan Turing y los límites de la computación”, Miguel Ángel Martín Delgado (Universidad Complutense de Madrid)
La computabilidad estudia qué problemas se pueden calcular y cuales no. Esto lleva a los límites mismos de lo que es cognoscible. Turing desarrolló la teoría de la computabilidad mediante la búsqueda de procedimientos mecánicos para calcular las cosas, y también ideó las definiciones adecuadas que definen los algoritmos.
Esta es la forma en la que la matemática debe ser entendida, en un nivel fundamental y partiendo de sus axiomas. Esto lleva a la noción misma de la creatividad matemática. Turing no sólo demostró qué cosas podemos calcular de una manera muy precisa y universal, sino que también demostró que hay cosas que no podemos calcular.
Después de observar los límites de la computabilidad la siguiente pregunta es: ¿podemos ir más allá? Esto depende de lo que se llama la barrera de Turing.
También se plantearán algunas alternativas a la computación de Turing, incluyendo la computación cuántica. Además se presentará con perspectiva histórica el trabajo de Turing, respecto a algunos de sus precursores, contemporáneos, y los matemáticos que después de él llevaron más lejos sus ideas.
Miguel Ángel Martín Delgado es profesor del Departamento de Física Teórica I de la Facultad de Ciencias Físicas de la Universidad Complutense de Madrid.
http://www.ucm.es/info/giccucm/PersonalMAMD/Research.html
- “Lógica, computación, representación del conocimiento y resolución de problemas”, David Pearce (Universidad Politécnica de Madrid)
Alan Turing sentó las bases sobre las que comenzó la larga relación entre la lógica y la ciencia de la computación. Desde la década de 1970 se ha ampliado, profundizado y diversificado en muchas direcciones nuevas. La lógica se convirtió en una fuente de inspiración para el diseño de lenguajes de programación, una herramienta para la especificación y la semántica, y un instrumento para verificar la exactitud de software.
También ha proporcionado idiomas para la reconstrucción de los conocimientos humanos y para modelar y automatizar muchas tareas de razonamiento humano. En esta charla se plantearán algunos de los trabajos actuales en la inteligencia artificial que usan la lógica de programación, resolución de problemas, la reconstrucción del conocimiento y el análisis de las sociedades artificiales.
David Pearce es investigador del Departamento de Inteligencia Artificial de la Universidad Politécnica de Madrid.
- “Alan Turing: el vínculo de Leibniz a Gödel”, Josep Díaz (Premio Nacional de Informática 2011, Universitat Politécnica de Catalunya)
La charla se divide en dos partes. En la primera parte, se examina la búsqueda de un procedimiento universal para resolver problemas. En la segunda, a partir de la carta de Gödel a von Neumann, se estudia el significado de la ‘inviabilidad’ a través del problema de la indecibilidad truncado, y se darán ejemplos de los problemas de diferentes campos en los que parece difícil de obtener procedimientos más eficientes.
Josep Díaz es profesor en el Departament de Llenguatges i Sistemes Informatics de la Universitat Politecnica de Catalunya.
http://www.lsi.upc.edu/~diaz/
- “Sobre el legado de Turing en la lógica matemática y los fundamentos matemáticos” – Joan Bagaria i Pigrau (ICREA Research Professor, Universitat de Barcelona)
Turing es muy conocido por su trabajo en ciencias de la computación y la criptografía, pero su impacto en la teoría general de las funciones computables (teoría de la repetición) y en los fundamentos de las matemáticas es de igual importancia. La conferencia se centrará en algunas de las ideas y los problemas derivados de su trabajo en estas áreas, tales como el análisis de la estructura de los grados de Turing y el desarrollo de las lógicas ordinales, que han sido de interés permanente hasta el día de hoy y que aún presentan enormes retos matemáticos.
Joan Bagaria i Pigrau es profesor de investigación en la Institució Catalana de Recerca i Estudis Avançats (ICREA) de la Universitat de Barcelona. Su campo de trabajo es la teoría de conjuntos.
Más información
El Simposio Internacional: ‘El legado de Alan Turing’, organizado por la Real Academia de Ciencias Exactas, Físicas y Naturales, tendrá lugar el 23 y 24 de octubre en la Fundación Areces. El encuentro reunirá a importantes investigadores en los campos de los que fue precursor el matemático Alan Turing. Entre los ponentes hay primeras figuras en campos como la inteligencia artificial, la lógica, la computación, la criptografía, y otros temas. El programa completo puede consultarse en la página de la Fundación Areces.
“Alan Turing y los límites de la ciencia”, Manuel Alfonseca, en el blog “El Año de Turing” en El País.
–
Ágata A. Timón es responsable de Comunicación y Divulgación del ICMAT
Compartir
Puzzle Bobble
Karate Blazers
Puzzle De Bloques
Magical Cat Adventure