La prueba de diagonalización de Turing es una versión de este juego en el que las preguntas recorren la lista infinita de algoritmos posibles, preguntando repetidamente: “¿Puede este algoritmo resolver el problema que nos gustaría demostrar que es incomputable?”
“Son una especie de ‘preguntas infinitas'”, dijo Williams.
Para ganar el juego, Turing necesitaba elaborar un problema en el que la respuesta fuera no para cada algoritmo. Eso significaba identificar una entrada particular que hace que el primer algoritmo genere una respuesta incorrecta, otra entrada que hace que el segundo falle, y así sucesivamente. Encontró esas entradas especiales usando un truco similar al que Kurt Gödel había usado recientemente para probar que afirmaciones autorreferenciales como “esta afirmación es indemostrable” significaban problemas para los fundamentos de las matemáticas.
La idea clave fue que cada algoritmo (o programa) se puede representar como una cadena de ceros y unos. Eso significa, como en el ejemplo del programa de comprobación de errores, que un algoritmo puede tomar el código de otro algoritmo como entrada. En principio, un algoritmo puede incluso tomar su propio código como entrada.
Con esta idea, podemos definir un problema no computable como el de la prueba de Turing: “Dada una cadena de entrada que representa el código de un algoritmo, genera 1 si ese algoritmo genera 0 cuando su propio código es la entrada; de lo contrario, la salida es 0”. Todo algoritmo que intente resolver este problema producirá una salida incorrecta en al menos una entrada, es decir, la entrada correspondiente a su propio código. Eso significa que este perverso problema no puede resolverse mediante ningún algoritmo.
Lo que la negación no puede hacer
Los informáticos aún no habían terminado con la diagonalización. En 1965, Juris Hartmanis y Richard Stearns adaptaron el argumento de Turing a probar que no todos los problemas computables son iguales: algunos son intrínsecamente más difíciles que otros. Ese resultado lanzó el campo de la teoría de la complejidad computacional, que estudia la dificultad de los problemas computacionales.
Pero la teoría de la complejidad también reveló los límites del método contrario de Turing. En 1975, Theodore Baker, John Gill y Robert Solovay demostrado que muchas cuestiones abiertas en la teoría de la complejidad nunca podrán resolverse únicamente mediante la diagonalización. El principal de ellos es el famoso problema P versus NP, que pregunta si todos los problemas con soluciones fácilmente comprobables también son fáciles de resolver con el ingenioso algoritmo adecuado.
Los puntos ciegos de la diagonalización son consecuencia directa del alto nivel de abstracción que la hace tan poderosa. La demostración de Turing no implicaba ningún problema incomputable que pudiera surgir en la práctica; en cambio, inventó un problema de ese tipo sobre la marcha. Otras pruebas de diagonalización están igualmente alejadas del mundo real, por lo que no pueden resolver cuestiones en las que los detalles del mundo real importan.
“Manejan la computación a distancia”, dijo Williams. “Me imagino a un tipo que se enfrenta a virus y accede a ellos a través de una guantera”.
El fracaso de la diagonalización fue una indicación temprana de que resolver el problema P versus NP sería un largo viaje. Pero a pesar de sus limitaciones, la diagonalización sigue siendo una de las herramientas clave en el arsenal de los teóricos de la complejidad. En 2011, Williams lo utilizó junto con una serie de otras técnicas para probar que cierto modelo restringido de computación no podía resolver algunos problemas extraordinariamente difíciles, un resultado que había eludido a los investigadores durante 25 años. Estaba muy lejos de resolver P versus NP, pero aun así representó un avance importante.
Si quieres demostrar que algo no es posible, no subestimes el poder de simplemente decir no.
historia original reimpreso con permiso de Revista Quanta, una publicación editorialmente independiente del Fundación Simons cuya misión es mejorar la comprensión pública de la ciencia cubriendo los desarrollos y tendencias de la investigación en matemáticas y ciencias físicas y biológicas.