Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarte el uso de la web mediante el análisis de tus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúas navegando, consideramos que aceptas nuestra Política de cookies .

ALAN TURING'S SYSTEMS OF LOGIC. THE PRINCETON THESIS.
Dirigido por Andrew W. Appel. Princeton University Press; Princeton, 2012.

Numerosas han sido las contribuciones realizadas en homenaje a Alan Turing, coincidiendo con el centenario de su nacimiento, en 1912. Al legado de este fundador de la ciencia de la computación y la inteligencia artificial ha dedicado la colección Temas de Investigación y Ciencia un número monográfico. De entre sus propios escritos el libro de cabecera es, sin lugar a dudas, la obra más interesante. Allí se avanzaron las ideas que resultaron decisivas para determinar el rumbo de la computación y la matemática.

Entró en el King’s College de Cambridge en 1931. De 1931 a 1934 se sintió atraído por diversas partes de la matemática, incluida la lógica matemática. En 1935 fue elegido fellow del King’s College, tras su disertación sobre teoría de la probabilidad, On the Gaussian error function, donde redescubría de forma independiente el teorema central del límite. A comienzos de ese año empezó a interesarse en problemas de lógica, con un curso impartido por M. H. A. Newman.

Uno de tales problemas era el de la decisión (Entscheidungsproblem), la cuestión de si existe un método eficaz para decidir, dada cualquier fórmula bien formada del cálculo de predicados de primer orden, si es o no válida en todas las interpretaciones posibles. Eso se había resuelto en afirmativo para determinadas clases especiales de fórmulas, pero el problema general seguía abierto en esa época. Se hallaba convencido de que la respuesta debía ser negativa, si bien para demostrar la imposibilidad de un procedimiento de decisión tendría que ofrecer una explicación matemática exacta de lo que significa ser computable mediante un proceso estrictamente mecánico.

A ese análisis llegó a mediados de abril de 1936, a través de lo que daría en llamarse máquina de Turing: un mecanismo ideal de computación subsiguiente a un elenco finito de instrucciones (un programa) en etapas discretas efectivas sin limitación de tiempo ni espacio. Plasmó su investigación en el artículo titulado «On computable numbers, with an application to the Entscheidungsproblem». Introdujo la idea de que la computación podía actuar sobre estructuras simbólicas generales, no necesariamente aritméticas. En particular, sacó partido del hecho de que un programa sea una de esas estructuras. Newman se mostró en un principio escéptico ante el análisis de Turing, pero luego se convenció y le animó a publicarlo. A los veinticuatro años había, pues, ideado un modelo universal de computación, o máquina de Turing, y demostrado su teorema de incompletitud, que hizo públicos en el artículo antes mencionado, con la corrección incorporada en 1937.

Kurt Gödel había formulado en 1931 la tesis de la incompletitud. Sus métodos (la codificación numérica de la sintaxis y el procesamiento numérico de la lógica) sentaron las bases para numerosas técnicas de ciencia de la computación. Estableció la teoría de las funciones recursivas. Se valió de los enteros para idear un lenguaje universal capaz de codificar computaciones arbitrarias y algoritmos generales que podrían demostrar teoremas. Por su parte, Alonzo Church había presentado el cálculo lambda como modelo de computación; de acuerdo con su tesis, las funciones recursivas caracterizan exactamente las funciones efectivamente calculables.

Muestra del genio de Gödel fue sustituir la idea informal de verdad por un concepto que podía formalizarse: la idea de prueba. Aplicando la noción formal de prueba, Gödel mostró que debía existir algún enunciado sobre los números que no podía ser ni demostrado ni contradicho utilizando las reglas de la deducción lógica, aunque podía verse que ese enunciado era cierto traspasando el sistema lógico y contemplando el enunciado desde una perspectiva metalingüística. Con otras palabras, el teorema de incompletitud de Gödel expresaba que existía en matemática un componente semántico irreductible. Turing continuaba la revolución de la lógica iniciada por Gödel. Describió su argumento matemático de manera similar a la empleada por el austríaco. Pero Turing abordó con éxito la cuestión planteada por Hilbert sobre la decidibilidad y lo hizo fundándose en un análisis filosófico enteramente original del concepto de computación.

Por recomendación de Newman, Turing decidió pasar un año estudiando con Church. Solicitó una beca Procter. Se la negaron. Hubo de contentarse con la exigua subvención de su King’s College. Llegó a Princeton a finales de septiembre de 1936. Allí, el departamento de matemáticas se había convertido ya en meca de referencia. En el Instituto de Estudios Avanzados estaban Albert Einstein, John von Neumann y Hermann Weyl, en el departamento Lefschetz. Profesores visitantes ese año fueron Courant y Hardy. En lógica esperaba encontrar, además de Church, a Gödel, Bernays, Kleene y Rosser. Gödel visitó el instituto en los años 1933, 1934 y 1935; acortó su última estancia, por enfermedad, y no volvió hasta 1939. Bernays había visitado Princeton en 1935-36; no volvió a Estados Unidos hasta después de la guerra. Kleene y Rosser habían recibido el doctorado por la época en que Turing llegó y habían buscado trabajo en otros sitios. Se vio pues limitado a asistir a las clases de Church que encontraba excesivamente precisas. No parece que intimaran.

Church reconocía en 1937 que en la exposición de Turing había tres nociones diferentes: computabilidad por una máquina de Turing, recursividad general en el sentido de Herbrand-Gödel-Kleene y definibilidad lambda en el sentido de Kleene y Church; de ellas, la primera tiene la ventaja de hacer evidente de inmediato la identificación con la eficacia en el sentido ordinario; la segunda y la tercera presentan la ventaja de la idoneidad para su incorporación en un sistema de lógica simbólica. Así nació lo que dio en llamarse tesis de Church-Turing; de acuerdo con la misma, las funciones efectivamente computables son exactamente las computables por la máquina de Turing.

¿Y la tesis de Princeton? En la primavera de 1937 Turning desarrolló una prueba más detallada sobre la equivalencia de la computabilidad de la máquina con la definibilidad lambda. Publicó también dos artículos sobre teoría de grupos; de ellos, el dedicado a aproximaciones finitas de grupos continuos llamó la atención de Von Neumann. El jefe del departamento de matemáticas, Luther P. Eisenhart, animó a Turing a pasar otro año en Princeton y solicitar de nuevo la beca Procter. En esta ocasión, avalado por Von Neumann, que ponderaba su trabajo sobre funciones casi periódicas y grupos continuos, logró la subvención, que le permitía dedicarse a su tesis doctoral sobre lógicas ordinales, dirigida por Church.

Aprobada en mayo de 1938 y publicada en 1939 con el título Systems of logic based on ordinals, la tesis constituía el primer intento sistemático de abordar la idea natural de superar la incompletitud godeliana de sistemas formales mediante la iteración de la agregación de enunciados, tales como la consistencia del sistema. De hecho, esas clases de iteraciones pueden extenderse hasta lo transfinito. Su principal resultado fue que podíamos obviar la incompletitud para una clase importante de enunciados aritméticos, aunque no para todos. Lo adelanta en la introducción: «El conocido teorema de Gödel revela que todo sistema de lógica es, en cierto sentido, incompleto, mas al propio tiempo aporta los medios por los que a partir de un sistema L de lógica puede obtenerse un sistema L’ más completo. Mediante la repetición del proceso, obtenemos la secuencia L, L1 = L’, L2 = L1... cada vez más completa que la anterior. Podría entonces construirse una lógica Lw en la que los teoremas demostrables fueran la totalidad de teoremas demostrables con la ayuda de las lógicas L, L1, L2... Procediendo de esta forma podemos asociar un sistema de lógica con cualquier ordinal constructivo. Podríamos preguntarnos si una tal secuencia de lógicas de este tipo es completa en el sentido de que a cualquier problema A le corresponde allí un ordinal a tal que A por medio de la lógica La». Valiéndose de un ingenioso argumento, Turing obtuvo un resultado de completitud parcial que reclamaba ulterior investigación. Reconocería problemas importantes en su lógica ordinal.

Tras la publicación de la tesis no volvió al tema de la misma. Al poco de su regreso a Inglaterra participó en la Escuela de Códigos y Cifras del Gobierno, que habría de llevarle hasta su trabajo secretísimo en Bletchley Park durante la guerra: abrir el código cifrado de la Marina alemana, empleando mecanismos de computación, aunque no máquinas de Turing. Tras la guerra puso en práctica sus ideas sobre computación al supervisar la construcción del ACE (Automatic Computing Engine) del Laboratorio Nacional de Física; redactó el plan detallado de funcionamiento. Mas su idea de un computador digital electrónico automático con almacenamiento interno de programas no pudo concretarse hasta después de su muerte, cuando el avance de la electrónica lo permitió.

En 1948 inventó el método de descomposición LU en la computación numérica. Dos años más tarde roturó el terreno de lo que sería la futura inteligencia artificial y realizó predicciones notablemente precisas sobre los derroteros que habrían de seguir computación y computadores. En 1952 se dejó atraer por la aparición de formas en las estructuras biológicas (pautas de las flores, simetría de los huesos o manchas de los tigres). Murió a los 42 años. Se cree que se suicidó angustiado por las normas inglesas dictadas contra la homosexualidad.

Puedes obtener el artículo en...

Revistas relacionadas

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.