En la década de los años veintes del siglo pasado, el famoso científico alemán David Hilbert propuso un proyecto de investigación que más tarde sería conocido como el ”programa de Hilbert”.

El objetivo último era la resolución de una crisis de carácter filosófico y meta-matemático llamada en alemán la Grundlagenkrise der Mathematik, la cual amenazaba con desmoronar los principios fundamentales en los que descansaba la Matemática conocida hasta ese entonces. La crisis se había originado como consecuencia del trabajo de diversos investigadores que conducían a importantes contradicciones y paradojas en cuerpos matemáticos que se consideraban bien establecidos y bien comportados (un ejemplo famoso de estos resultados es la paradoja de Bertrand Russell, en la que éste demostró que la teoría informal de conjuntos de Georg Cantor contenía una contradicción que podía ser construida a partir de sus propios axiomas).

Para resolver esta crisis Hilbert propuso en 1928, durante el Congreso Internacional de Matemáticas celebrado en Bologna, tres preguntas concretas. La primera se refería a si acaso la Matemática podía formularse como un sistema completo, en el sentido de que cualquier enunciado matemático (tal como decidir si la raíz cuadrada de dos es o no un número racional) pudiera ser demostrado formalmente, o refutado. La segunda pregunta planteaba si la Matemática era consistente en el sentido de que para cualquier sistema fuese imposible arribar a contradicciones (tales como “1+2 = 4” en la aritmética de los enteros), derivadas de aplicar pasos matemáticos correctos a partir del conjunto de axiomas que definían al sistema. Finalmente, Hilbert planteó la pregunta de si acaso la Matemática era decidible en el sentido de que pudiera demostrarse que para cualquier aseveración debía existir algún método o algoritmo capaz de decidir en un tiempo finito acerca de la validez de tal afirmación. Aunque Hilbert no pudo demostrarlo, su opinión e intuición se inclinaban firmemente hacia la idea de que sus tres preguntas podrían algún día ser contestadas afirmativamente.

Kurt Gödel
Kurt Gödel

Sin embargo, muy poco tiempo después del anuncio del programa de Hilbert, en septiembre de 1930, el joven prodigio austríaco Kurt Gödel sacudió inolvidablemente a la comunidad matemática al anunciar en una conferencia celebrada en la ciudad de Könisberg, sus teoremas de incompletitud. Allí, Gödel demostró que: (1) Si un sistema formal es consistente entonces no puede ser completo, (2) Si un sistema formal es inconsistente entonces debe ser completo y, (3) La consistencia de un sistema axiomatizable formalmente no puede ser probada desde dentro del mismo sistema. Una consecuencia directa de estos resultados es que las respuestas correctas a las primeras dos preguntas de Hilbert eran un sonoro: ¡no!.

La comunidad de lógica matemática suele considerar a los teoremas de incompletitud de Gödel como una de las cúspides científicas más altas jamás alcanzadas por el intelecto humano.

Por otro lado, la respuesta a la tercera pregunta de Hilbert, denominada técnicamente como el Entscheidungsproblem, permaneció como un problema abierto a la investigación, hecho que despertaría la imaginación de un joven y brillante estudiante de matemáticas de la Universidad de Cambridge, quien la asumiría como un estimulante reto intelectual que se volvería su permanente obsesión en los años por venir. El nombre de aquel joven matemático era Alan Mathison Turing.

turingninoDesde niño, Turing había estado fascinado por un sueño infantil que hoy, en la cómoda perspectiva que brinda más de un siglo de distancia, nos podría parecer lejano, remoto y extravagante. Turing soñaba que un día él podría convertirse en un famoso inventor de máquinas de escribir. Con el tiempo, la vida le concedería su deseo de una manera tan rotunda como hermosa, y además, por partida doble.

El método de ataque que Turing empleó para contestar la tercera pregunta de Hilbert, esto es, el problema de determinar si la Matemática es o no decidible, fue la de diseñar teóricamente un autómata que fuera capaz de ejecutar cualquier programa de manera mecánica.

Fue así como Turing concibió las capacidades de cómputo asociadas a una hipotética máquina de escribir, la cual estaría equipada con una cinta de tamaño infinito que contendría las instrucciones y los datos del programa a ser ejecutado. El operador humano, llamado por Turing “el computador’”, sería el encargado de “ejecutar” el programa. Para ello, el computador podría leer, escribir y navegar sobre la cinta, con la capacidad de modificar a cada paso los valores almacenados en ella.

Turing demostró rigurosamente que aunque existen una infinidad de números reales que son computables, existen muchos más que no lo son.

Turing decidió entonces simular, en su autómata, la ejecución de una instancia del problema de decisión de Hilbert, a través del siguiente ingenioso mecanismo matemático: utilizando el argumento de la diagonal de Cantor, Turing demostró rigurosamente que aunque existen una infinidad de números reales que son computables, existen muchos otros más (tantos que ni siquiera son enumerables), los cuales pertenecen a la clase de números no computables. Lanzando la estocada final, Turing demostró además que el problema de escribir un número no computable es en sí no computable (pues si lo fuera, dejaría de ser, el número escrito, no computable).

Con la abrumadora evidencia que le brindaba ese brillante contra-ejemplo, Turing encontró que la respuesta correcta a la tercera pregunta de Hilbert era una vez más, y para la mayúscula sorpresa de todos, negativa.

Tan fundamental le pareció a Turing el hallazgo y definición de números computables y no computables, que decidió titular el artículo en que publicó su investigación como:

“On computable numbers, with an application to the Entscheidungsproblem”,

título que podría traducirse a nuestro idioma como: “Acerca de los números computables y de su aplicación al Entscheidungsproblem”. Como mera curiosidad, vale la pena recordar aquí que un primer rechazo editorial a ese artículo se debió a que un revisor juzgó inapropiado su título por llevar una palabra en alemán. Este trabajo es considerado el Magnus Opus de Alan Turing.

Es imprescindible señalar que la respuesta negativa a la pregunta planteada por el Entscheidungsproblem, conlleva profundas resonancias filosóficas, pues demuestra formalmente la existencia de problemas que no podrían ser resueltos por ninguna entidad inteligente sin importar si ésta dispone de recursos de cómputo infinitos ni si dicha entidad puede esperar por toda una eternidad para que se produzcan las soluciones a tales problemas. Entre otras cosas, la existencia de números no computables demuestra matemáticamente la no existencia de dioses todopoderosos, y, más mundanamente, define las cotas superiores de nuestra capacidad como civilización para resolver problemas de manera efectiva.

En el momento histórico en que Turing propuso su singular máquina de escribir, todavía no se conocían formalmente los conceptos de algoritmos o programas.

Significativamente, en el momento histórico en que Turing propuso su singular máquina de escribir, todavía no se conocían formalmente los conceptos de algoritmos o programas. De hecho, la construcción física de la primera computadora tendría lugar casi una década después de la publicación de su gran artículo, pues sería hasta el 21 de junio de 1948 cuando por primera vez se ejecutó un programa en una computadora electrónica: la Manchester Mark 1, cuya puesta en marcha estuvo a cargo de un grupo de ingenieros y matemáticos de la Universidad de Manchester. En ese proyecto, el propio Alan Turing fungió como uno de los principales colaboradores, actuando oficiosamente como programador en jefe de dicha computadora, posición que aprovechó para inventar, definir y/o utilizar técnicas fundamentales de los lenguajes de programación modernos, tales como: sentencias con saltos condicionales, ciclos, subrutinas, etc.

Turing hizo contribuciones invaluables al desarrollo de la computación como ciencia, formalizando los conceptos de algoritmos, programas y lenguajes de computación, etc. Asimismo, ideó algoritmos que hoy son valorados como procedimientos clásicos, tales como la descomposición matricial LU, y la proposición e impulso de la subdisciplina conocida modernamente como inteligencia artificial.

La naturaleza curiosa de Turing lo llevó a hacer contribuciones fundamentales.

La naturaleza curiosa de Turing lo llevó a hacer contribuciones fundamentales en la morfogénesis dentro de la disciplina de biología matemática y a escribir el primer programa que podía jugar ajedrez a pesar de no tener una computadora donde ejecutarlo físicamente. Debido a ello, Turing simuló su ejecución haciendo él mismo las veces del ordenador que jugaba contra la esposa de un amigo. De acuerdo a la leyenda, el programa de Turing perdió su primera (y por muchísimos años única), partida de ajedrez.

Alan Turing fue condenado en el año de 1952 por sus conductas homosexuales.

En uno de los hechos más oscuros de la conservadora sociedad inglesa de la época, Alan Turing fue condenado en el año de 1952 por sus conductas homosexuales (en una situación trágicamente similar a la que a principios de siglo había padecido el escritor y dramaturgo irlandés Oscar Wilde), a ser castrado químicamente. Se ha conjeturado que la depresión que esta situación le causó lo impulsó a suicidarse el 8 de junio de 1954, a la edad de 41 años.

Juego de rotores de la máquina de escribir Enigma
Juego de rotores de la máquina de escribir Enigma

Más de veinte años después de su muerte, documentos desclasificados del sistema de inteligencia militar inglés mostraron de manera inesperada que Turing fue el principal criptógrafo de su país durante la segunda guerra mundial. Los análisis de probabilidad de Turing y su habilidad para construir computadoras electromecánicas fueron factores claves para que un equipo especializado de cripto-analistas ingleses lograra romper la famosa máquina criptográfica alemana “Enigma”, lo que permitió que los ingleses pudieran leer durante años los despachos confidenciales intercambiados por el ejército y marina alemanes. Se considera que el rompimiento de Enigma fue una de los principales razones por las cuales las fuerzas aliadas de Estados Unidos, Inglaterra y Francia lograron vencer junto con la ayuda del poderoso ejército rojo de la Unión Soviética, a la Alemania nazi de Adolf Hitler.

Tres máquinas de escribir Enigma (exhibidas en el museo nacional de Criptología de Washington D.C, EUA)
Tres máquinas de escribir Enigma (exhibidas en el museo nacional de Criptología de Washington D.C, EUA)

Como puede apreciarse en la figura, Enigma es una máquina de escribir con un juego de cinco rotores que permite crear cifrados a través de la progresiva permutación de tales rotores. Es muy curioso que una vez más el sueño infantil de Turing de jugar con máquinas de escribir se volviera realidad. Aunque en esta ocasión, la máquina de escribir Enigma representó el formidable reto criptogrófico que Turing debía resolver para salvaguardar el destino de su país.

Máquina electromecánica llamada Bomb, ideada por Turing para vulnerar Enigma (exhibida en el museo nacional de Criptología de Washington D.C, EUA)
Máquina electromecánica llamada Bomb, ideada por Turing para vulnerar Enigma (exhibida en el museo nacional de Criptología de Washington D.C, EUA)

El 23 de junio de 2012 se cumplieron cien años del natalicio del científico inglés Alan Mathison Turing. Con motivo de este acontecimiento se organizaron alrededor del mundo una serie de festejos celebrando el legado intelectual que Turing nos heredó en diversas ramas de la ciencia, muy especialmente, en el área de las ciencias computacionales. Concluimos este breve ensayo brindando a la salud de la enorme obra científica e intelectual de Alan Turing, quien es sin duda una de las personalidades académicas más subyugantes y únicas que el siglo pasado produjo. C2

(a)
Máquina de escribir tradicional
2
Máquina de escribir hipotética conocida como máquina de Turing
3
Detalle de la cinta de almacenamiento de la máquina de Turing

Sobre el autor

Miembro del Sistema Nacional de Investigadores, nivel 2. Investigador titular en | Website

Sus principales áreas de investigación son criptografı́a, aritmética computacional y seguridad informática.

POR:

francisco@cs.cinvestav.mx

Sus principales áreas de investigación son criptografı́a, aritmética computacional y seguridad informática.

3 Comentario

    • Francisco Rodríguez Henríquez -

    • 14 junio, 2016 / 22:21 pm

    Gracias por ambos comentarios. Es muy interesante que se haya demostrado la teoría de Turing con respecto a la formación de patrones biológicos.

    • A. Tejeda -

    • 17 mayo, 2016 / 21:01 pm

    Excelente articulo de divulgación. Muy bien escrito, capta la atención e invita a seguir leyendo.

    • Dra Lorenza Gonzalez Mariscal -

    • 17 mayo, 2016 / 10:47 am

    En la pasada reunión anual de la Sociedad Americana de Biología celular celebrada en Diciembre del 2015 en San Diego, el Dr S. Kondo de la Universidad de Osaka, demostró que la teoría matemática de AM Turing de formación de patrones biológicos, includidos los de la piel en los animales (e.g. piel de cebra, cheetah, peces etc), es correcta. Este planteamiento teórico hecho por Turing hace 60 años, se confirmó al analizar las intracciones entre las células pigmentadas: melanóforos y Xantóforos, en la piel del pez cebra.

Deja un Comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *