El Legado de Alan M. Turing (I)

el legado de turing 1Por: Ramón López de Mántaras**/Tendencias21.net

Con motivo del centenario de su nacimiento, en enero de 2012 la prestigiosa revista Nature calificó a Alan Turing como “one of the top scientific minds of all time”. No es difícil estar de acuerdo con esta afirmación.

En 1954, cuando Turing murió, los ordenadores estaban todavía en su tierna infancia. Sus contribuciones fueron prácticamente olvidadas durante casi 20 años, en parte por su homosexualidad, por lo que fue injustamente condenado lo cual le condujo al suicidio, y en parte también por el secreto que rodeó su trabajo en Bletchley Park.

A finales de los años 70, poco después de que la homosexualidad dejara de ser un crimen en el Reino Unido, y después de que se desclasificaran las actividades de Bletchley Park, el legado de Turing empezó a ser reconocido. Además de sus extraordinarias capacidades para descifrar mensajes, Turing es considerado uno de los “padres” de la Informática.

En 1936, es decir, mucho antes de que se construyeran los primeros ordenadores electrónicos, desarrolló los fundamentos teóricos de la computación.

Además, Turing es considerado también el “padre” de la Inteligencia Artificial (IA). En un artículo publicado en 1950, Turing argumentaba que en un plazo de unos 50 años habría ordenadores inteligentes capaces de llevar a cabo deducciones lógicas, de aprender adquiriendo nuevos conocimientos, tanto inductivamente como por experiencia y evolución, y capaces de comunicar mediante interfaces humanizadas. Esta idea era muy radical en aquel momento y de hecho es un debate que todavía persiste.

Por si fuera poco, además de estas fundamentales contribuciones a la computación y a la IA, Turing formuló hace 60 años una teoría sobre la morfogénesis para explicar cómo se generan los patrones biológicos que dan lugar, por ejemplo, a las rayas en los tigres o las manchas en los leopardos.
En este artículo intentaré dar algunos detalles de estas tres impresionantes contribuciones de Turing. Empecemos pues por su contribución a los fundamentos teóricos de la computación.

Conceptos teóricos de los ordenadores

A la edad de 24 años, Turing, publicó en la revista “Proceedings of the London Mathematical Society” los conceptos teóricos sobre los que se basan todos los ordenadores actuales. En efecto, la máquina de Turing es una rigurosa formalización de conceptos tan básicos en informática como el concepto de algoritmo y el concepto de calculabilidad y gracias a estos conceptos determinó donde están los límites de lo que es calculable por un ordenador.

Demostrar imposibilidades es de importancia extraordinaria en ciencia. Por ejemplo, la imposibilidad de construir máquinas con movimiento perpetuo condujo al descubrimiento de las leyes de la termodinámica en física.

De la misma forma, conocer los límites de las matemáticas y de la computación nos puede enseñar algunas reglas básicas acerca de sus posibilidades o, como muy bien dice el matemático Gregory Chaitin, nos permite saber cuándo no debemos intentar lo imposible.

Turing, de hecho, no pretendía inventar un modelo teórico de los ordenadores modernos. Lo que quería era resolver un problema en lógica matemática llamado “Entscheidungsproblem” o problema de la decisión, formulado en 1928 por David Hilbert.

Por aquel entonces los matemáticos estaban investigando sobre los fundamentos de la matemática y Hilbert planteó la pregunta de si todo enunciado matemático (como por ejemplo “2+2=4”) era decidible o no.

En otras palabras, ¿existe un procedimiento mecánico paso a paso tal que dado cualquier enunciado matemático permita determinar si éste es cierto o falso?

Bien que la respuesta es obvia para el enunciado “2+2=4”, sabemos que hay muchos enunciados cuya respuesta requiere esfuerzos extraordinarios (por ejemplo el último teorema de Fermat) y muchos otros que todavía no tienen respuesta como por ejemplo la conjetura de Riemann, que tiene que ver con la distribución de los números primos, que data de 1859 y, aunque todo el mundo sospecha que es cierta, todavía no se ha podido demostrar.

Incluso el propio Turing dedicó grandes esfuerzos en intentar demostrarla y estaba convencido que los ordenadores jugarían un papel importante en su demostración.

Procedimiento paso a paso

Si existiera un procedimiento tal que, dado un enunciado matemático, permitiera determinar si éste es cierto o falso, entonces todas las grandes cuestiones de las matemáticas podrían ser resueltas. Hilbert confiaba en que dicho procedimiento existiera.

De hecho lo que él llamaba “procedimiento mecánico pasa a paso” hoy día lo llamamos “algoritmo” y por lo tanto lo que Hilbert buscaba era de hecho  un programa de ordenador. Turing así lo intuyó y para poder intentar responder a la pregunta de Hilbert, tuvo que definir previamente que es un “procedimiento pasa a paso” y que tipo de dispositivo lo podría llevar a cabo. No se trataba de construir materialmente dicho dispositivo, sino de especificar claramente su funcionamiento.

Inicialmente especificó una máquina capaz de leer y escribir sobre una cinta de papel (que puede ser infinita). El cabezal lector/escritor de la máquina en cada paso lee un símbolo contenido en la cinta y en función del valor de este símbolo y de su estado interno toma una decisión acerca de qué acción hacer a continuación siguiendo un conjunto de reglas internas.

El repertorio de acciones es muy sencillo: desplazar la cinta hacia la izquierda o hacia la derecha, borrar el símbolo leído, escribir un símbolo, o parar. Esta máquina es lo que conocemos ahora cómo “Máquina de Turing”.

El problema era que al tener un conjunto fijo y predefinido de reglas internas no servía para dar respuesta a la pregunta de Hilbert sobre la decidibilidad.

La genialidad de Turing le permitió darse cuenta que era posible usar la propia cinta para introducir en la máquina el conjunto de reglas internas que determinaran su funcionamiento. Gracias a ello, la máquina se convertía en programable y por consiguiente podía simular cualquier otra máquina con reglas fijas. Esta nueva máquina, que actualmente llamamos “Máquina Universal de Turing”, no es otra cosa que un ordenador.

Ahora ya sí, Turing tenía su ordenador teórico con el cual poder responder a la pregunta: ¿qué es calculable? Es decir ¿qué es lo que puede y no puede hacer un ordenador? Para responder la pregunta de Hilbert, Turing buscaba un contraejemplo, es decir una expresión concreta de forma que la máquina no pudiera determinar ni su certeza ni su falsedad.

La cuestión que permitió a Turing resolver el problema es: ¿Puede una máquina examinar cualquier programa y decidir si se detendrá, dando una respuesta, o bien nunca se detendrá?. En otras palabras, ¿puede un ordenador determinar si es cierto o falso que cualquier programa se detendrá? Turing demostró que la respuesta a esta pregunta es NO y por consiguiente el procedimiento mecánico paso a paso deseado por Hilbert no existe y el Entscheidungsproblem de Hilbert quedó resuelto.

Turing no había únicamente logrado resolver el problema de la decisión formulado por Hilbert sino que, de paso y sin realmente pretenderlo, había establecido los fundamentos teóricos de la computación.

**Director del Instituto de Investigación en Inteligencia Artificial (IIIA), perteneciente al Consejo Superior de Investigaciones Científicas.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s