Supongamos que alguien le pidiera que ideara la computadora más poderosa posible.
por RENE PERALTA
Alan Turing, cuya reputación como figura central en la informática y la inteligencia artificial solo ha crecido desde su prematura muerte en 1954, aplicó su genio a problemas como este en una época anterior a que existieran las computadoras tal como las conocemos. Su trabajo teórico sobre este problema y otros sigue siendo una base de la computación, la IA y los estándares criptográficos modernos, incluidos los que recomienda el NIST.
El camino desde el diseño de la computadora más poderosa posible hasta los estándares criptográficos tiene algunos giros y vueltas, al igual que la breve vida de Turing.
Alan Turing
Crédito: © National Portrait Gallery, Londres
En la época de Turing, los matemáticos debatieron si era posible construir una sola máquina multipropósito que pudiera resolver todos los problemas que son computables
Por ejemplo, podemos calcular la ruta más eficiente energéticamente de un automóvil a un destino y( en principio) la forma más probable en que una cadena de aminoácidos se doblará en una proteína tridimensional. Otro ejemplo de un problema computable, importante para el cifrado moderno, es si los números más grandes se pueden expresar o no como el producto de dos números más pequeños. Por ejemplo, 6 se puede expresar como el producto de 2 y 3, pero 7 no se puede factorizar en enteros más pequeños y, por lo tanto, es un número primo.
Algunos matemáticos prominentes propusieron diseños elaborados para computadoras universales que funcionarían siguiendo reglas matemáticas muy complicadas. Parecía abrumadoramente difícil construir tales máquinas. Se necesitó el genio de Turing para demostrar que una máquina muy simple podría, de hecho, calcular todo lo que es computable.
Su hipotético dispositivo ahora se conoce como una «máquina de Turing». La pieza central de la máquina es una tira de cinta, dividida en cajas individuales. Cada caja contiene un símbolo (como A, C, T, G para las letras del código genético) o un espacio en blanco. La tira de cinta es análoga a los discos duros actuales que almacenan bits de datos. Inicialmente, la cadena de símbolos en la cinta corresponde a la entrada, que contiene los datos para el problema a resolver. La cadena también sirve como memoria de la computadora. La máquina de Turing escribe en la cinta los datos a los que necesita acceder más adelante en el cálculo.
Crédito: NIST
El dispositivo lee un símbolo individual en la cinta y sigue las instrucciones sobre si cambiar el símbolo o dejarlo solo antes de pasar a otro símbolo. Las instrucciones dependen del «estado» actual de la máquina. Por ejemplo, si la máquina necesita decidir si la cinta contiene la cadena de texto «TC», puede escanear la cinta en la dirección hacia adelante mientras cambia entre los estados «la letra anterior era T» y «la letra anterior no era C». Si mientras está en el estado «la letra anterior era T» se lee una «C», va a un estado «la encontró» y se detiene. Si se encuentra con el símbolo en blanco al final de la entrada, va al estado «no lo encontró» y se detiene. Hoy en día reconoceríamos el conjunto de instrucciones como el programa de la máquina.
Tomó algún tiempo, pero finalmente quedó claro para todos que Turing tenía razón: la máquina de Turing podía calcular todo lo que parecía computable. Ningún número de adiciones o extensiones a esta máquina podría ampliar su capacidad informática.
Para entender lo que se puede calcular, es útil identificar lo que no se puede calcular. En una vida anterior como profesor universitario tuve que enseñar programación varias veces. Los estudiantes a menudo se encuentran con el siguiente problema: «Mi programa ha estado funcionando durante mucho tiempo; ¿está atascado?» Esto se llama el Problema de La Detención, y los estudiantes a menudo se preguntaban por qué simplemente no podíamos detectar bucles infinitos sin quedarnos atrapados en ellos. Resulta que un programa para hacer esto es una imposibilidad. Turing demostró que no existe una máquina que detecte si otra máquina se detiene o no. A este resultado seminal le siguieron muchos otros resultados de imposibilidad. Por ejemplo, los lógicos y filósofos tuvieron que abandonar el sueño de una forma automatizada de detectar si una afirmación (como si hay infinitos números primos) es verdadera o falsa, ya que eso es incomputable. Si pudiera hacer esto, entonces podría resolver el problema de detención simplemente preguntando si la afirmación «esta máquina se detiene» es verdadera o falsa.
Turing continuó haciendo contribuciones fundamentales a la IA, la biología teórica y la criptografía. Su participación en este último tema le trajo honor y fama durante la Segunda Guerra Mundial, cuando jugó un papel muy importante en la adaptación y extensión de las técnicas criptoanalíticas inventadas por los matemáticos polacos. Este trabajo rompió el cifrado de la máquina alemana Enigma, haciendo una contribución significativa al esfuerzo de guerra.
Turing era gay. Después de la guerra, en 1952, el gobierno británico lo condenó por tener relaciones sexuales con un hombre. Se mantuvo fuera de la cárcel solo sometiéndose a lo que ahora se llama «castración química». Murió en 1954 a los 41 años por envenenamiento con cianuro, que inicialmente se dictaminó como un suicidio, pero puede haber sido un accidente según análisis posteriores. Pasarían más de 50 años antes de que el gobierno británico se disculpara y lo «perdonara» (después de años de campaña de científicos de todo el mundo). Hoy en día, el honor más alto en ciencias de la computación se llama el Premio Turing.
El trabajo de computabilidad de Turing proporcionó la base para la teoría moderna de la complejidad. Esta teoría trata de responder a la pregunta «Entre esos problemas que pueden ser resueltos por una computadora, ¿cuáles pueden ser resueltos de manera eficiente?» Aquí, «eficientemente» significa no en miles de millones de años, sino en milisegundos, segundos, horas o días, dependiendo del problema computacional.
Por ejemplo, gran parte de la criptografía que actualmente salvaguarda nuestros datos y comunicaciones se basa en la creencia de que ciertos problemas, como la descomposición de un número entero en sus factores primos, no se pueden resolver antes de que el Sol se convierta en una gigante roja y consuma la Tierra (actualmente se pronostica para 4 mil millones a 5 mil millones de años). El NIST es responsable de los estándares criptográficos que se utilizan en todo el mundo. No podríamos hacer este trabajo sin la teoría de la complejidad.
La tecnología a veces nos arroja una curva, como el descubrimiento de que si se construye una computadora cuántica lo suficientemente grande y confiable, sería capaz de factorizar enteros, rompiendo así parte de nuestra criptografía. En esta situación, los científicos del NIST deben confiar en los expertos del mundo (muchos de ellos internos) para actualizar nuestros estándares. Hay razones profundas para creer que las computadoras cuánticas no podrán romper la criptografía que el NIST está a punto de implementar. Entre estas razones está que la máquina de Turing puede simular computadoras cuánticas. Esto implica que la teoría de la complejidad nos da límites sobre lo que una poderosa computadora cuántica puede hacer.
Pero ese es un tema para otro día. Por ahora, podemos celebrar cómo Turing proporcionó las claves de gran parte de la tecnología informática actual e incluso nos dio pistas sobre cómo resolver los problemas tecnológicos que se avecinan.
Ciberseguridad, Tecnologías de la Información y Matemáticas y Estadística
René Peralta, AUTOR DE ESTA NOTA Original de NIST
René Peralta recibió una licenciatura en Economía de Hamilton College en 1978. En 1980 recibió una maestría en Matemáticas de la Universidad Estatal de Nueva York en Binghamton. En 1985 recibió un doctorado
Alan Turing
Crédito: © National Portrait Gallery, Londres