Què és una màquina de Turing?

La noción de máquina de Turing es una idealización matemática útil para probar que ciertas tareas no son automatizables o que ciertas funciones no son compatibles. Una máquina de Turing es como un computador digital, pero sin limitaciones de capacidad de memoria ni de tiempo de ejecución. Una función es computable si, y sólo si, hay una máquina de Turing que la computa: si le damos uno o varios argumentos como input, la máquina ejecuta una serie finita de pasos programados e imprime como output el valor de ta función para esos argumentos. Un conjunto es recursivo si la correspondiente función característica (que asigna el número 1 a los objetos que pertenecen al conjunto y 0 a los que no) es computable. Estas nociones fueron introducidas hace 60 años por el genial y extravagante matemático inglés Alan Turing en Sobre números computables (1937), y constituyen desde entonces la basé de la teoría de la recursión, la rama más exitosa de la lógica-matérnática.En 1939 estalló la Segunda Guerra Mundial y Turing fue enrolado para descifrar los códigos secretos del Ejército alemán. Los mandos alemanes creían que las órdenes cifradas que transmitían a sus aviones y submarinos eran indescifrables, pero Turing y sus colegas lograron descifrarlas con una enorme y primitiva máquina computadora, lo cual resultó decisivo para la victoria aliada.

¿Puede pensar una máquina? Turing planteó la cuestión en 1947 ante el National Physical Laboratory, y tres años después, en un artículo, Máquinas computadoras e inteligencia, iniciando así la investigación de la inteligencia artificial. Turing sostenía que esta cuestión sólo puede resolverse experimentalmente y proponía lo que luego se ha llamado el test de Turing: podemos decir que una máquina piensa si un interlocutor humano, comunicándose por es crito con ella y con otros humanos, es incapaz de distinguir a la máquina de los otros interlocutores humanos. Otros retos, como la simulación de partidas de ajedrez o la prueba creativa de teoremas, también han sido propuestos. Turing pensaba que en 50 años (es decir, ahora) empezaría a ser posible construir máquinas asi.

Hace tiempo que los computadores realizan pruebas matemáticas triviales, del tipo de los ejercicios que se ponen a los estudiantes, pero se dudaba de su capacidad para encontrar pruebas originales de problemas teóricos que hayan resistido a matemáticos profesionales. A finales de 1996, Larry Wos y William McCune (del Argomié National Laboratory) han logrado por primera vez programar un computador de tal manera que ha resuelto creativamente un problema abierto que los matemáticos humanos habían sido incapaces de resolver. Herbert Robbins había planteado a Alfred Tarski la pregunta de si cierto sistema de ecuaciones era equivalente a la definición de un álgebra de Doole. Tarski no había sabido resolverlo, pero se o había pasado a otros matemáticos hasta que finalmente legó a manos de Wos y McCune, que trabajan en progra- as de prueba automática de teoremas. Un nuevo programa genérico (no específico para el problema de Robbins), que trata de probar hipótesis mediante la búsqueda de contradicciones implicadas por la negación de la hipótesis, a conducido por sorpresa a encontrar una prueba original de la conjetura de Robbins.

Turing se habría alegrado de este resultado, que confirma sus predicciones. También se habría alegrado de lo mucho que se han liberalizado las costumbres. En 1952 no quiso negar una relación homosexual que había tenido, por lo que fue condenado judicialmente a una pena de cárcel, conmutada por un tratamiento de hormonas que lo dejó impotente y le estropeó su buena forma, física, que él siempre había cuidado con gimnasia y carreras de maraón. Deprimido, se suicidó en 1954, a los 42 años de edad.

Jesús Mosterín, ¿Puede pensar una máquina?, El País, 19/02/997