El Año de Turing

El Año de Turing

La informática a la que recurrimos para tuitear o hacernos una resonancia magnética es en esencia Alan Turing, uno de los científicos más importantes de la Historia. Fue un hombre generoso que afrontó con genialidad lógica horrores como el Nazismo pero al que el mundo devolvió sólo injusticia. Acercamos su obra a los lectores para que comprueben lo importante que fueron sus aportaciones. Creó la Informática tal y como la conocemos.

A propósito de Turing: Ciencia básica frente a ciencia aplicada

Por: | 14 de febrero de 2013

HECTOR GEFFNER

Correo electrónicoPocos problemas tienen un carácter más teórico que determinar si hay más conjuntos de números naturales que números naturales, si una axiomatización de la lógica de predicados captura todas inferencias que son deductivamente válidas, o  si puede existir un procedimiento que demuestre que una inferencia es válida o no. Estos problemas no parecen tener mucho que ver con temas más profanos como envíar mensajes de texto, comprar entradas para un concierto por internet, o jugar al World of Warcraft (WoW). Sin embargo, estos y otros desarrollos prácticos que influyen de foma profunda en nuestra vida cotidiana están íntimamente vinculados a esos problemas teóricos mencionados inicialmente.

David HilbertEl vínculo se encuentra en los computadores desarrollados a partir de la década de los años 40, siguiendo un diseño que –en sus líneas fundamentales– había sido esbozado años atrás por el lógico matemático Alan Turing. Se trata de la famosa "máquina de Turing", que no fue diseñada para hacer nada práctico, aunque posteriormente Turing viera las posibilidades que tal "máquina" abría para el estudio del comportamiento inteligente. La "máquina de Turing", en papel, fue desarrollada para resolver un problema eminentemente teórico: el problema de encontrar un procedimiento para determinar la validez de una inferencia en lógica de predicados.  El problema había sido planteado por un famoso matemático, David Hilbert, en 1928. The Universal ComputerTanto la formulación del problema por Hilbert, como su resolución por Turing, se apoyan en ideas desarrolladas por Hilbert y otros lógicos y matemáticos, entre los que cabe destacar a Boole, Cantor, Frege, Russell, y Godel; el "dream team" de la lógica moderna. La historia de este desarrollo está magníficamente contada en el libro "The Universal Computer: The Road from Leibniz to Turing", Martin Davis [1].

Turing demuestra rigurosamente que el procedimiento buscado por Hilbert no existe. Turing inventa "su" máquina como formalización de lo que es un procedimiento (un método de cómputo), y demuestra entonces que no puede haber tal máquina para el problema de Hilbert (el Alan Turingllamado "Entscheidungsproblem"[2], para diferenciarlo de otros problemas fundamentales también formulados por Hilbert). Para la prueba utiliza la idea de codificar máquinas con números, siguiendo el ejemplo de Godel quien introduce una idea similar para demostrar la incompletitud de la aritmética formal (otro problema planteado por Hilbert), y la  técnica de diagonalización, introducida antes por Cantor para demostrar que hay más conjuntos de naturales que números naturales, usada tambien por Godel en su prueba.

Turing no se queda en ese resultado sin embargo y construye una "máquina de Turing" (todavía en papel) que es "universal" en el sentido que este "hardware" particular puede ejecutar cualquier procedimiento. Más precisamente, esta máquina universal de Turing es programable: acepta la descripción de una máquina particular que resuelve un problema dado sobre una entrada, y emula el comportamiento de esa máquina sobre esa entrada.  Máquina de TuringLa máquina universal de Turing es la madre del computador programable moderno. Que algo así era incluso posible no era obvio en los años 40 cuando los "computadores" se desarrollaban para resolver un conjunto específico de cáculos. El límite de la  máquina universal de Turing, por otro lado, es el límite de ordenadores actuales, el límite de lo computable.

Sorprende ver como un desarrollo que no estuvo motivado en modo alguno por aplicaciones "prácticas", ha tenido un impacto que quizás algun día se compare al desarrollo de la agricultura. La historia, sin embargo, no es inusual en el desarrollo de la ciencia, donde uno sabe donde empieza pero no donde termina. Esa es la promesa de la ciencia desde el punto de vista social, y la aventura del  científico desde el punto de vista personal.

Hector Geffner es investigador senior ICREA y profesor de la Universitat Pompeu Fabra.


[1] Martin Davis es un matemático estadounidense, bien conocido por el algoritmo de Davis-Putnam para resolver el problema de satisfactibilidad booleana. Su libro “The Universal Computer” fue editado por Norton el el año 2000, y ha sido reeditado por Taylor & Francis en 2011.

Una excelente conferencia de Martin Davis sobre la naturaleza de la computación y los trabajos de Church y Turing se puede ver aquí. .

[2]  El "Entscheidungsproblem" fue resuelto de forma independiente por Alonzo Church y Alan Turing, en sendos artículos publicados en 1936 con pocos meses de diferencia. El artículo de Turing contenía la descripción de su “máquina”, lo que tuvo una inmensa repercusión posterior. Como curiosidad, cuando Turing escribió su artículo había terminado sus estudios de matemáticas en Cambridge (Reino Unido) pero no había comenzado sus estudios de doctorado. Alonzo Church fue el director de su tesis doctoral en Princeton (Estados Unidos).

Hay 4 Comentarios

Enhorabuena por este blog, cada apunte que se publica confirma la importancia monumental que tuvo Alan Turing para la informática. Lástima que en muchas carreras de ingeniería en informática no se le preste la atención necesaria.

si te gusta ser informado visita el website http://newshub.es/ que es un portal de noticias actualizadas en tiempo real en mas de 40 categorias. todo quality

Me encanta el post, y creo que la escasa visión práctica (o tal vez, por el contexto del post, debería decir teórica) de las políticas científicas pueden llevar (o tal vez están ya llevando) al fomento de la obtención de resultados puramente prácticos. Hay una viñeta muy buena y muy ilustrativa en:
http://www.nuevarevista.net/sites/default/files/imagecache/wysiwyg_imageupload_lightbox_preset/wysiwyg_imageupload/19/c_g.png

✓✓✓ (TUTORIAL): Como PERDER 10 KG Con Un Simple Consejo: http://su.pr/2we2i5

Los comentarios de esta entrada están cerrados.

Sobre los autores

Este blog es una obra colectiva en la que participarán científicos y expertos españoles y extranjeros cuya obra haya bebido de las aportaciones de Alan Turing. Aunque principalmente recogerá los avances científicos en la Informática, abarcará otras opiniones sobre la importancia de la misma en otros ámbitos: la Medicina, la Física, la Política, la Economía. El blog está coordinado por Pedro Meseguer y Juan José Moreno Navarro.

Archivo

julio 2013

Lun. Mar. Mie. Jue. Vie. Sáb. Dom.
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

El País

EDICIONES EL PAIS, S.L. - Miguel Yuste 40 – 28037 – Madrid [España] | Aviso Legal