Tesis de Church-Turing

Cuando se dice “este problema no se puede resolver con ninguna computadora”, hay un supuesto escondido. El resultado formal dice que no lo resuelve una máquina de Turing; el salto a “ninguna computadora” es la tesis de Church-Turing, y no es un teorema.

Cuatro caminos que dieron lo mismo

En los años treinta, varias personas atacaron por separado la pregunta de qué es un procedimiento efectivo. Church definió el cálculo lambda; Gödel y Herbrand, las funciones recursivas; Turing, su máquina; Post, otro sistema de reglas.

Los formalismos no se parecen en nada entre sí. Y sin embargo se demostró que definen exactamente el mismo conjunto de funciones computables. Esa convergencia desde puntos de partida tan distintos es la evidencia principal a favor de la tesis.

Qué afirma, y por qué no es un teorema

La tesis afirma que toda función que un ser humano puede calcular siguiendo un procedimiento mecánico —sin creatividad, con papel y lápiz y tiempo ilimitado— es computable por una máquina de Turing.

No se puede demostrar porque uno de los lados no es un objeto matemático: “procedimiento mecánico” es una noción informal. Es una afirmación sobre la adecuación de un modelo a la realidad, más parecida a una ley física que a un teorema.

Es lo que le da alcance a los resultados negativos

Importa porque es lo que le da alcance a los resultados negativos. Sin la tesis, el problema de la parada sería una limitación de un formalismo particular; con ella, es una limitación de cualquier método efectivo.

También es lo que permite trabajar cómodo. Nadie escribe máquinas de Turing para demostrar que algo es computable: se describe el algoritmo en castellano y se invoca la tesis. Esa licencia es estándar y está apoyada en décadas sin contraejemplos.

Todos los lenguajes computan lo mismo

El resultado práctico de esa equivalencia es que todos los lenguajes de programación de propósito general computan lo mismo. Las diferencias entre ellos son de expresividad, de ergonomía y de rendimiento, nunca de poder de cómputo.

El cálculo lambda, además, no quedó como curiosidad histórica: es la base teórica de la programación funcional, y los sistemas de tipos de Haskell o ML descienden directamente de ahí.

La versión extendida, que sí se puede discutir

Hay una versión más ambiciosa, la tesis extendida: todo modelo razonable de cómputo simula a una máquina de Turing con una pérdida sólo polinomial. Eso es lo que permite hablar de la clase P sin aclarar el modelo.

Esa versión sí está bajo discusión. La computación cuántica no viola la tesis original —no computa nada incomputable— pero podría violar la extendida, porque resuelve la factorización en tiempo polinomial y no se conoce ningún algoritmo clásico que lo haga. Si eso se confirma, lo que cambia es qué es tratable, no qué es computable.

Los modelos que la superarían

Se han propuesto modelos hipercomputacionales —máquinas que ejecutan infinitos pasos en tiempo finito, o que acceden a un oráculo— que superarían el límite. Todos requieren supuestos físicos que nadie sabe cómo realizar.

Mientras tanto, la tesis sigue sin contraejemplo después de noventa años, y ese es el estado real del asunto: no está demostrada, no está en duda seria, y es la que sostiene el significado práctico de todo lo que se dice sobre lo incomputable.

Qué afirma exactamente, y qué no

Cierre

Cuatro formalismos independientes definieron el mismo conjunto de funciones, y de ahí salió la tesis: lo efectivamente calculable es lo computable por una máquina de Turing. No es demostrable porque uno de sus términos es informal, y es lo que convierte los resultados de imposibilidad en afirmaciones sobre cualquier computadora.