Opinión

El Código Enigma: Alan Turing y el nacimiento de la ciencia de la computación

Mauricio Bustamante

Mauricio Bustamante

PhD en Física. Center for Cosmology and AstroParticle Physics, The Ohio State University.

Turing trabajó también como criptólogo durante la II Guerra Mundial, descifrando el código con el que la Alemania Nazi cifraba sus mensajes. Se interesó también por la inteligencia artificial, y la prueba más famosa en ese campo lleva su nombre.

La primera mitad del siglo XX fue una época de gigantes intelectuales en la ciencia y las matemáticas. Las primeras dos décadas del siglo vieron nacer la teoría de la relatividad especial, la relatividad general, la mecánica cuántica y el descubrimiento de la estructura del ADN. Hacia la década de 1940, apareció una nueva cepa de matemáticos, de notable habilidad y creatividad, que inventaron la noción moderna de computadora y se convirtieron en los padres de la nueva ciencia de la computación. Al hacerlo, además, dieron respuesta a preguntas sobre los fundamentos de las matemáticas que tuvieron profundas consecuencias.

El británico Alan Turing (1912-1954) fue miembro de esa nueva estirpe. Matemático de notable habilidad, se convirtió en una de las figuras preeminentes de la historia de la computación. El problema central que atacó Turing fue el llamado Entscheidungsproblem, o “problema de decisión”. Para resolverlo, veremos que Turing inventaría la noción formal de lo que es una computadora.
El problema había sido planteado por el gran matemático David Hilbert en 1928. Consistía en lo siguiente: dado un conjunto de axiomas -es decir, de preceptos incuestionables sobre los que basar cualquier deducción- ¿es posible deducir todas las consecuencias (o teoremas) que de este se derivan? En otras palabras, el Entscheidungsproblem era el problema de si es posible juzgar a cualquier enunciado, sea cual sea, como verdadero o como falso. La respuesta que encontró Turing, e independientemente Alonzo Church, fue negativa: existen enunciados que no pueden ser catalogados como verdaderos o como falsos. Este resultado, conocido como la “tesis Church-Turing”, junto con los descubrimientos de otro de los grandes matemáticos del siglo XX, Kurt Gödel, sería responsable de resquebrajar la hasta entonces sólida estructura de las matemáticas.

La ingeniosa forma en que Turing dio respuesta al problema de decisión constituye el fundamento de la teoría de computación moderna. Turing inventó la siguiente máquina abstracta. Imagínense una cinta de papel de extensión infinita, dividida en recuadros, cada uno de los cuales puede estar vacío o contener un símbolo, digamos, un número o el símbolo de una operación aritmética (“+”, “-”, “x”, “/”). Estos símbolos serán los datos de entrada (input) y de salida (output) de la máquina.

Existe, además, un cabezal que se desliza sobre la cinta, hacia la izquierda o hacia la derecha, y que tiene la capacidad de examinar el recuadro de la cinta que se encuentre debajo de él. Dentro del cabezal se encuentran guardadas instrucciones que le indican qué hacer, dependiendo de cuál sea el símbolo que lea en el recuadro. Por ejemplo, si leyera el símbolo “+”, sus instrucciones le indicarían que debe moverse una posición hacia la derecha, luego leer el número X que encuentre en el nuevo recuadro, guardarlo en su memoria interna, moverse otra posición hacia la derecha, leer el número Y que ahí encuentre y añadirlo al que acababa de leer, moverse una posición más a la derecha y escribir en ese nuevo recuadro el resultado de la suma X + Y. El cabezal puede contener tantas instrucciones diferentes como podamos imaginar, y la cinta puede asimismo contener cualquier secuencia de símbolos. Entre más grande sea el conjunto de instrucciones del cabezal, más rico será el comportamiento de la máquina de Turing. En efecto, podemos identificar al cabezal de la máquina con la unidad central de procesamiento (CPU) de nuestras computadoras modernas; a la cinta, con su memoria; y a la secuencia de símbolos escrita en la cinta, con los programas -o secuencias de instrucciones- que la computadora ejecuta.

La máquina de Turing es un modelo matemático de cómo funciona una computadora: cualquier operación que una computadora de escritorio puede realizar, puede realizarla también una máquina de Turing abstracta que tenga suficiente complejidad en su juego de instrucciones. Sin embargo, Turing fue un paso más allá: como parte de su solución al problema de decisión, definió qué es, en principio, computable y qué no lo es. En otras palabras, qué tipos de programas pueden ser ejecutados por una computadora: esta podrá computar únicamente aquellos programas que también puedan ser computados por una máquina de Turing.

En una primera mirada, esta es una afirmación inofensiva. Pero tiene implicancias sustanciales, que resultan estar conectadas al problema de decisión. En concreto, excepto en casos especiales, resulta que no es posible predecir si un programa terminará de ejecutarse, o si la computadora, o la máquina de Turing, continuará ejecutándolo sin fin. Los programas que podrían predecir si otros programas se detendrán se conocen como oráculos y Turing encontró que no existen, excepto en casos particularmente sencillos. Esto quiere decir que, en general, no hay forma de predecir si un programa se ejecutará exitosamente; debemos inevitablemente ejecutarlo, o computarlo, para saber si lo hará. Al demostrar esto, Turing había demostrado también, por analogía, que existen enunciados cuya verdad o falsedad no puede ser determinada, dando así respuesta al problema de decisión. El trabajo fundamental de Turing en las bases de la informática teórica lo colocan con justicia como uno de los padres de la ciencia de la computación, junto al ya mencionado Alonzo Church y a otro matemático brillante, John von Neumann, que modeló a su manera el proceso de computación.

Turing trabajó también como criptólogo durante la II Guerra Mundial, descifrando el código con el que la Alemania Nazi cifraba sus mensajes. Se interesó también por la inteligencia artificial, y la prueba más famosa en ese campo lleva su nombre. El “test de Turing” consiste en que un entrevistador humano sostenga un diálogo escrito con un interlocutor cuya identidad permanece velada: al entrevistador no se le dice de antemano si su interlocutor es otro humano, o si es una inteligencia artificial. Si el entrevistador es incapaz de distinguir entre las dos posibilidades, a partir del diálogo, entonces la inteligencia artificial pasa la prueba. El interés de Turing lo llevó además a explorar la biología matemática, en especial, la formación de patrones visibles en seres vivos, como en las pieles de los leopardos y de otros animales. Sus estudios teóricos sobre la química de la formación de patrones fueron comprobados experimentalmente décadas luego de su muerte.

Alan Turing fue una de las grandes mentes del siglo pasado. Ocurrió que fue homosexual y que vivió en una época en la que estas relaciones eran consideradas ofensas criminales en el Reino Unido. En 1952 fue sometido por el Estado a un tratamiento hormonal para intentar reducir su libido, y esto precipitó su aparente suicidio. El mundo perdió de forma cruel a una de sus mentes más lúcidas. En el 2013, el Reino Unido finalmente se disculpó públicamente y concedió el perdón real a Turing. Haríamos bien en tener presente que el género, la etnia, la religión y la orientación sexual no deben ser obstáculos para el desarrollo intelectual de nuestra especie. Convivimos diariamente con los frutos tangibles del trabajo de Turing, un hombre que alcanzó la grandeza a pesar, y no gracias, a las circunstancias que le tocó vivir.

El jueves 19 de marzo los Coloquios de Física presentarán la conferencia Alan Turing y la formación de patrones a cargo del profesor Desiderio Vásquez. Revisa la información en nuestra Agenda PUCP.