Turing i els límits de la ciència.

A finales del siglo XIX, los científicos se convencieron de que la ciencia llegaría algún día a explicarlo todo. Lo que estaba ocurriendo en las diversas ramas de las ciencias exactas y de la naturaleza parecía confirmarlo:

• En matemáticas, Gottlob Frege abordó la formalización completa de la aritmética, pensando que, a partir de unos pocos axiomas indudables, y aplicando unas reglas de deducción sencillas, sería posible demostrar todo lo demás. 
• En física se extendió bastante la idea de que ya lo sabíamos todo. Sólo quedaban dos pequeños detalles que explicar: por qué la radiación del cuerpo negro no tenía la distribución predicha por la teoría, y por qué el experimento de Michelson-Morley parecía indicar que la velocidad de la luz en el vacío es constante, independientemente de la dirección en que se mida. Una vez resueltos esos dos problemas, podríamos dar por cerrada esa rama de la ciencia. 
• En química, a medida que se iban llenando los huecos de la tabla periódica, cada vez quedaban menos elementos por descubrir. Pronto se llenarían todos, con lo que también esa rama de la ciencia podría darse por concluida.

La primera en descubrir que esas previsiones estaban equivocadas fue la física. En la primera década del siglo XX, los dos fenómenos mencionados dieron lugar, no a un ligero ajuste, sino a dos reorganizaciones totales de las teorías físicas (la relatividad y la mecánica cuántica), que además parecen ser incompatibles entre sí. El fin de la física estaba muy lejos. Quizá en el infinito...

Las matemáticas fueron la segunda ciencia que descubrió sus límites. En 1902, Bertrand Russell echó abajo el trabajo de Frege al descubrir la paradoja que lleva su nombre. Y cuando Russell intentó subsanarla,  tropezó en 1931 con el teorema de Gödel , que esencialmente viene a decir que todo sistema formal consistente y con potencia semejante a la aritmética elemental no es completo (contiene proposiciones verdaderas que no se pueden demostrar). Con otras palabras, que hay teoremas que es imposible demostrar, aunque sean ciertos.

Finalmente, hacia los años cuarenta la química descubrió los elementos transuránidos, que añadían un número indefinido de casillas a la tabla periódica y abrieron una nueva búsqueda que parece no tener fin.
Alan Turing participó de forma importante en la investigación sobre los límites de la ciencia. En 1935 formuló el famoso teorema de la parada, que en el fondo es equivalente al teorema de Gödel, pero que resulta más fácil de entender intuitivamente, pues se aplica al campo de las máquinas de cómputo. En este contexto, debemos distinguir dos cosas distintas:

• El problema de la parada, un problema concreto que Turing formuló.
• El teorema de la parada, resuelto por Turing, que demuestra que el problema de la parada no tiene solución.

Turing diseñó un tipo especial de máquina de cómputo que, en su honor, se llama máquina de Turing. Aunque no se construye con hardware, resulta fácil de simular con una computadora electrónica. Cada máquina de Turing está diseñada para ejecutar un solo programa. Sin embargo, Turing demostró que es posible diseñar una máquina especial (la máquina de Turing universal), que es capaz de simular el funcionamiento de cualquier otra máquina de Turing si se le proporcionan, como datos de entrada, la definición de esta y su input (los datos de entrada de la máquina simulada).

La máquina de Turing universal tiene una capacidad de cálculo equivalente a la de nuestras computadoras electrónicas. En puridad, es aun más potente, porque se supone que tiene memoria infinita. Pero esta diferencia se está haciendo cada vez menos importante, a la vista del tamaño que alcanza la memoria de las computadoras modernas.

Igual que pasa con los programas de ordenador, cuando una máquina de Turing se pone en marcha pueden ocurrir dos cosas: que acabe parándose, cuando ha terminado el trabajo, o que se meta en un bucle permanente del que no pueda salir. En el caso de un ordenador, cuando ocurre esto tenemos medios para interrumpir el programa desde fuera, para evitar que el aparato se bloquee. En las máquinas de Turing, que son abstractas, esto no está previsto.
Veamos el problema de la parada, tal como lo formuló Turing: Supongamos que conocemos la descripción de una máquina de Turing, que incluye el programa que esa máquina ha sido diseñada para ejecutar, y los datos de entrada que recibe. Antes de ponerla en marcha, ¿es siempre posible predecir si, cuando lo hagamos, llegará a pararse o se meterá en bucle cerrado?

Parece un problema sencillo, pero Turing demostró que la respuesta es negativa. No siempre es posible hacer esa predicción. Por supuesto, para las máquinas sencillas sí se puede. Pero el problema de la parada pregunta si la predicción puede hacerse siempre.

Turing lo demostró por reducción al absurdo: supuso que el problema de la parada tiene solución y llegó a una contradicción. Por lo tanto, la hipótesis es falsa. Veamos una demostración intuitiva del teorema de la parada:

1. Supongamos que el problema de la parada tiene solución.
2. Entonces, es posible programar una máquina de Turing para resolverlo. Sus datos de entrada serán la descripción de la máquina de la que queremos predecir si se para, y los datos de entrada de esta. La máquina contestará SI (si la otra máquina se va a parar con esos datos) o NO (si no se va a parar con esos datos).
3. Ahora modificamos la construcción de la máquina que resuelve el problema de la parada. En vez de contestar SI, hacemos que se meta en un bucle del que no pueda salir. Cuando tenga que contestar NO, hacemos que se pare. (Este cambio es muy sencillo).
4. Por último, le damos a esta máquina la descripción de ella misma y le preguntamos si se para o no. Con la modificación que hemos hecho, si la máquina se va a parar, en vez de responder SI debe meterse en un bucle, es decir, no se debe parar. Si no va a pararse, debe pararse. Pero esto es una contradicción. Luego la hipótesis inicial es falsa. Luego el problema de la parada no tiene solución.

Alan Turing demostró, de una manera nueva y muy elegante, que el conocimiento humano tiene límites infranqueables, que hay problemas que no se pueden resolver. Deberíamos recordarlo.

Manuel Alfonseca, Alan Turing y los límites de la ciencia, El año de Turing, 04/10/2012