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 computables. 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 la 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 le pertenecen) es computable. Estas nociones fueron introducidas hace sesenta años por el genial y extravagante matemático inglés Alan Turing en "Sobre números computables" (1937), y constituyen desde entonces la base de la teoría de la recursión.

Una función computable puede definirse también como función recursiva (véase la definición al final, como apéndice). Da igual. Toda definición recursiva es Turing-computable, y a la inversa, toda función computable en el sentido de Turing es recursiva. El hecho de que las nociones de recursividad y computabilidad de Turing coincidan (aun partiendo de ideas iniciales bien distintas), de que todas las otras precisiones de la noción de computabilidad propuestas por otros autores (como Post, Markov y Church) hayan resultado también equivalentes, y de que toda función conocida y computable en sentido intuitivo sea también Turing-computable, ha llevado a la conclusión (conocida como tesis de Church) de que el concepto intuitivo de computabilidad queda perfectamente precisado por la noción de computabilidad de Turing (o de recursividad). Mientras que tenemos varias nociones incompatibles de conjunto o de consecuencia o inferencia (y, por tanto, teorías de conjuntos y lógicas alternativas), la teoría de la recursión o de la computabilidad parece haber dado unívocamente en el clavo. En este sentido puede afirmarse que es la rama más exitosa de la lógica matemá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.

Una máquina universal de Turing U es una máquina de Turing capaz de simular el comportamiento de cualquier otra máquina de Turing M en el sentido de que, si introducimos en U como input la tabla de M (digamos, m) y el argumento x, entonces U(m,x) = M(x) para cualquier x, es decir, U produce como output el mismo resultado que M (y eso ocurre con cualquier máquina M). Los actuales computadores son casi máquinas universales de Turing; sólo les falta tener memoria ilimitada para serlo del todo. El primer computador (o "cerebro electrónico", como entonces se decía) universal (no diseñado para una tarea específica) fue el ENIAC, que hizo su primera demostración pública en Philadelphia en 1946. Al año siguiente, en 1947, Turing planteó la cuestión ¿Puede pensar una máquina? ante el National Physical Laboratory (de Inglaterra) y tres años depués en un artículo, "Máquinas computadoras e inteligencia", iniciando así la investigación en 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 escrito 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 cincuenta años (es decir, ahora) empezaría a ser posible construir máquinas capaces de enfrentarse a ellos. ¿Hasta qué punto se han cumplido sus predicciones?

El juego de ajedrez siempre ha sido considerado como el más difícil e intelectual de todos los juegos, y los grandes maestros del ajedrez han sido admirados por su gran inteligencia y creatividad estratégica. Alan Turing y su amigo David Champernowne eran grandes aficionados al ajedrez. Ellos inventaron (todavía medio en broma) el primer programa para jugar al ajedrez, Turochamp. En 1950 Claude Shannon (el fundador de la teoría de la información) ya esbozó la estrategia para construir un computador capaz de jugar al ajedrez. En 1967 apareció el programa Mc Hack, que permitió por primera vez a un computador competir (aunque poco brillantemente) en un campeonato humano de ajedrez. Sin embargo, todos estos intentos estaban aún lejos de poder medirse con la habilidad de un gran maestro. Sin embargo, a mediados de los años 80 científicos de la Universidad Carnegie Mellon (de Pittsburgh) empezaron a trabajar en serio en un programa potente de ajedrez. Luego se trasladaron al centro de investigación Thomas Watson de la IBM (en el estado de New York), donde se les unieron otros expertos. Tras varios años de arduo trabajo, lograron programar a Deep Blue, un potente computador con 32 procesadores trabajando en paralelo y varios chips específicos, que le permiten considerar múltiples desarrollos futuros posibles y evaluar millones de configuraciones por segundo.

Finalmente, en febrero de 1996 se celebró la esperada confrontación entre Deep Blue y Garry Kasparov, el campeón del mundo de ajedrez, considerado como el mejor ajedrecista de todos los tiempos. Deep Blue sorprendió a todos los observadores ganando la primera partida. Garry Kasparov ganó la segunda, empató en la tercera y finalmente derrotó a la maquina. Todavía (aunque por los pelos) se mantenía la supremacía de la intuición humana sobre la capacidad computacional de la máquina. En mayo de 1997 volvió a repetirse el encuentro. Los científicos habían trabajado durante el año transcurrido en perfeccionar a Deep Blue y sus programas, con ayuda de un gran maestro. Si el año anterior Big Blue podía escanear 100 millones de posiciones por segundo, en 1997 llegaba ya a los 200 millones. Si el año anterior Kasparov había aprovechado ciertos fallos de la máquina, en 1997 habían sido corregidos. La dramática confrontación acabó con la derrota de Kasparov y la victoria de los programadores de Big Blue, que se embolsaron los 700.000 dólares de premio. Si incluso el gran Kasparov perdió su desafío contra el computador Big Blue, ya no hay ajedrecista en el mundo que se le pueda resistir.

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 Argonne National Laboratory) lograron por primera vez programar un computador de tal manera que resolviera creativamente un problema abierto que los matemáticos humanos habían sido incapaces de resolver.

En efecto, en 1933 E. Huntington había presentado una definición de álgebra de Boole que incuía (además de la conmutatividad y la asociatividad) la siguiente ecuación: n(n(x)+y)+n(n(x)+n(y)) = x. Su discípulo H. Robbins reemplazó esa ecuación de Huntington por otra algo más simple: n(n(n+y)+n(x+n(y))) = x. A los sistemas que satisfacen esa nueva ecuación (además de la conmutatividad y la asociatividad) se les llamó álgebras de Robbins. Es fácil comprobar que toda álgebra de Boole es un álgebra de Robbins. Robbins conjeturó que también vale la inversa, es decir, que toda álgebra de Robbins es un álgebra de Boole, pero ni él mismo, ni Huntington, ni siquiera Tarski pudieron probar ni refutar dicha conjetura. Tarski planteó el problema a otros matemáticos que lo visitaban, y así fue pasando de unos a otros, sin que nadie lo solucionara. S. Winker se dedicó a investigar el tema desde 1980, y en 1992 probó que un álgebra de Robbins que satisfaga la condición de que hay un x y un z tales que n(x+z) = n(x) es también un álgebra de Boole. El 10 de octubre de 1996, el programa de prueba automática EQP ("equational prover"), diseñado y dirigido por William McCune (del Argonne National Laboratory, en Illinois), probó que cada álgebra de Robbins satisface la condición de Winker. Lo probó indirectamente, obteniendo automáticamente una contradicción a partir de la conjunción de la ecuación de Robbins con la negación de la condición de Winker. Con eso quedaba demostrado que toda álgebra de Robbins es un álgebra de Boole. El problema abierto de la matemática pura cuya solución había escapado a tantos matemáticos famosos había sido finalmente resuelto por un computador.

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 maratón. Deprimido, se suicidó en 1954, a los 42 años de edad.

APÉNDICE

Definición de las funciones recursivas.

La mayoría de las funciones numéricas (de números naturales o secuencias de números naturales en números naturales) familiares, como adición, multiplicación, exponenciación, factorial, máximo, mínimo, etc., pertenecen a una clase especialmente simple y rica a la vez de funciones computables: la clase de las funciones recursivas primitivas.

Las funciones recursivas primitivas son las funciones numéricas obtenibles a partir de las funciones recursivas primitivas iniciales (la función constante 0-aria C = 0, la función del siguiente, s(x) = x+1, y para cada dos números naturales n e i (1 < i < n), las funciones n-arias de identificación del i-ésimo miembro de una secuencia de n números, Iⁿ_i(x₁ ... x_n) = x_i) mediante un número finito de aplicaciones de los procesos de definición por substitución y de definición por inducción.

Sea g una función r-aria (r > 1) y sean h₁ ... h_r funciones n-arias (n > 0). Decimos que la función n-aria f está definida por substitución con ayuda de g,h₁ , ... h_r si y sólo si para cualesquiera números naturales x₁ ... x_n ocurre que:

f(x₁ ... x_n)= g(h₁(x₁ ... x_n), ...,h_r(x₁ ... x_n))

Sea g una función n-aria (n > 0) y sea h una función n+2-aria. Decimos que la función n+1-aria f está definida por inducción con ayuda de g yh si y sólo si para cualesquiera números naturales x₁ ... x_n, y ocurre que:

f(x₁ ... x_n, 0) = g(x₁ ... x_n)

f(x₁ ... x_n, s(y)) = h(x₁ ... x_n, y, f(x₁ ... x_n))

Aunque todas las funciones recursivas primitivas son computables, no todas las funciones computables son recursivas primitivas. Por ejemplo, la siguiente función f, definida por Ackermann en 1928, es computable en sentido intuitivo (y Turing-computable), pero no recursiva primitiva (recuérdese que s es la función del siguiente):

f(0,y) = s(y)

f(s(x),0) = f(x,1)

f(s(x), s(y)) = f(x, f(s(x),y))

Una noción más amplia es la de función recursiva, cuya definición requiere la previa introducción del operador µ (el mínimo ... tal que). Hablando de números naturales, µxø(x) es el mínimo número x que satisface la condición ø. Si hay algún número que satisface ø, y para cada número natural x es decidible si ø(x) o no, entonces µxø(x) es computable. Decimos que una función n-aria h es definible por mimalización a partir de una función n+1-aria f en caso normal si y sólo si para cada x1...xn existe al menos un w tal que f(x₁...x_n, w) = 0, y ocurre que para cada x₁...x_n:

h(x₁...x_n) = µw[f(x₁...x_n, w) = 0]

Una función recursiva es una función definible a partir de las funciones recursivas primitivas iniciales por un número finito de definiciones por sustitución, por inducción y por mimalización en caso normal.

La función de Ackermann es recursiva. De hecho toda función computable conocida es recursiva. Y se puede probar el siguiente teorema: Una función es recursiva si y sólo si es Turing-computable.

Regresar a la página principal