Ningún programa puede leer otro programa y decidir si terminará algún día.
No es una limitación de potencia de cálculo, es una imposibilidad demostrada en 1936.
Imagina un programa que recibe como entrada cualquier otro programa, junto con los datos que va a procesar, y responde una sola cosa, si terminará en algún momento o se quedará dando vueltas para siempre. Sería la herramienta más útil que un programador podría tener. No existe, y no existirá nunca, y eso no depende de cuánto mejoren los ordenadores. Está demostrado que cualquier programa así conduce a una contradicción lógica.
La demostración llegó en 1936, cuando no existía todavía ningún ordenador que ejecutara programas almacenados. La firmaron dos matemáticos por separado y con métodos distintos, y lo que establecieron no fue un límite técnico de su época sino una frontera permanente. Hay preguntas sobre el comportamiento de los programas que ningún algoritmo puede responder, y la lista de esas preguntas resultó ser mucho más larga de lo que nadie esperaba.
Hilbert quería un procedimiento que decidiera si una fórmula lógica es válida.
Church publicó la respuesta unos meses antes que Turing, y la respuesta era que no existe.
David Hilbert y Wilhelm Ackermann plantearon en 1928, en su manual de lógica teórica, lo que se conoce como el Entscheidungsproblem, el problema de la decisión. Pedían un procedimiento que, dada cualquier fórmula de la lógica de primer orden, determinara en un número finito de pasos si esa fórmula es universalmente válida. Conviene precisar el alcance, porque la divulgación lo agranda con frecuencia, no se trataba de un método para resolver toda la matemática, sino de una pregunta concreta sobre validez lógica. En 1931, Kurt Gödel ya había demostrado que ningún sistema formal consistente y axiomatizable de forma efectiva puede demostrar todas las verdades de la aritmética, pero su resultado no cerraba el problema de Hilbert, porque faltaba algo previo, definir con precisión qué es un procedimiento efectivo.
En 1936 llegaron dos definiciones distintas y la misma respuesta. Alonzo Church, con su cálculo lambda, publicó primero, en una nota de apenas dos páginas en el Journal of Symbolic Logic donde establecía que el Entscheidungsproblem no tiene solución. Alan Turing, que trabajaba sin conocer ese resultado, leyó su artículo ante la London Mathematical Society el 12 de noviembre de ese mismo año, y al enterarse añadió un apéndice demostrando que su noción de computabilidad y el cálculo lambda de Church describían exactamente la misma clase de funciones. Esa equivalencia es lo que Stephen Kleene bautizó después como tesis de Church-Turing. La versión popular que presenta a Turing resolviendo el problema en solitario no se sostiene, lo resolvió de forma independiente y llegó segundo a la imprenta. Demostrar que algo es imposible tiene su propio valor, el mismo que TecnoTimes describió al escribir sobre el disco de Festo y cuándo descifrar puede ser matemáticamente imposible.
Turing no escribió nunca la palabra parada en aquel artículo.
Demostró algo equivalente y el nombre llegó veinte años después.
Lo que Turing construyó primero fue una definición. Una máquina abstracta con una cinta infinita dividida en casillas, un cabezal que lee y escribe símbolos, un conjunto finito de estados y una tabla de reglas que dice qué hacer en cada combinación de estado y símbolo leído. La tesis de Church-Turing sostiene que cualquier procedimiento efectivo de cálculo puede expresarse mediante un modelo equivalente a una máquina de Turing. Sobre esa definición demostró que ciertas preguntas no tienen respuesta algorítmica, y la técnica que usó fue la diagonalización, suponer que existe la máquina que decide y construir con ella un caso que se contradice a sí mismo.
El detalle histórico que casi nadie cuenta es que Turing no habló de parada. Trabajó con máquinas que llamó circulares y libres de círculo, y demostró la indecidibilidad del problema de impresión, si una máquina llegará a escribir alguna vez un símbolo determinado. El nombre problema de la parada procede de Martin Davis, que lo usaba en sus clases en la Universidad de Illinois hacia 1952 y lo fijó en su libro de 1958. Un artículo de Joel David Hamkins y Theodor Nenu publicado en enero de 2026 en el Journal of Logic and Computation repasa exactamente esta cuestión y concluye que, aunque Turing no lo enunció, el problema de impresión es computablemente equivalente al de la parada y él aportó todas las ideas centrales, así que puede decirse que lo demostró en esencia.
La forma más intuitiva de entender qué significa esto es la que TecnoTimes planteó al escribir sobre los números primos y el orden que parece azar. Un sistema puede ser completamente determinista, sin una sola pizca de azar en sus reglas, y aun así negarse a revelar su resultado salvo que se ejecute entero, paso por paso, hasta el final. La diferencia es que con los primos siempre puedes seguir calculando. Con un programa que quizá no termina, ejecutarlo hasta el final puede no ser una opción.
Rice demostró en 1953 que el problema no era la parada, era cualquier propiedad del comportamiento.
Todo lo que se pueda afirmar sobre lo que hace un programa, y no sobre cómo está escrito, resulta indecidible.
Henry Gordon Rice generalizó el resultado en un artículo publicado en las Transactions of the American Mathematical Society en 1953, procedente de su tesis doctoral. Su corolario dice que toda propiedad semántica no trivial de la función que un programa computa es indecidible. Las dos condiciones importan. Semántica significa que la propiedad depende solo del comportamiento, de qué hace el programa con cada entrada, y no de cómo está escrito, de modo que dos programas distintos que computen lo mismo tienen que recibir el mismo veredicto. Contar cuántas líneas tiene un código o si usa una instrucción concreta son propiedades sintácticas y sí se pueden decidir. No trivial significa que al menos un programa cumple la propiedad y al menos uno no la cumple, porque si la cumplen todos o ninguno la respuesta es una constante.
El alcance práctico es considerable y conviene formularlo con precisión, porque suele contarse mal. De Rice se sigue directamente que no existe ningún algoritmo capaz de decidir si un programa arbitrario cumple una especificación cualquiera. Para la detección de virus y para el análisis estático en general, los resultados de imposibilidad existen igualmente pero se demuestran por reducción directa al problema de la parada, no invocando a Rice. Fred Cohen lo estableció para los virus informáticos en 1987 con un argumento elegante, si existiera un procedimiento que decide si un programa es un virus, bastaría con escribir un programa que consulte ese procedimiento y se comporte como virus exactamente cuando el procedimiento diga que no lo es. William Landi hizo lo propio para el análisis estático en 1992.
Por eso todo antivirus y todo analizador estático general tiene que trabajar con aproximaciones, y no por dejadez de sus fabricantes. En análisis estático, una herramienta puede intentar no omitir determinados comportamientos posibles del programa, pero para conseguirlo debe sobreaproximar y termina señalando también casos que en la ejecución real nunca producirían un fallo. Otras herramientas sacrifican esa garantía para reducir el número de falsas alarmas y obtener resultados más útiles en la práctica. No existe un analizador universal capaz de decidir con exactitud todas las propiedades relevantes de cualquier programa, y esa limitación explica buena parte de lo que TecnoTimes contó sobre por qué tu terminal es una invitación al desastre cada vez que instalas un paquete.
En 2024 hubo que descartar ciento ochenta y un millones de máquinas de Turing para demostrar un solo número.
El castor afanoso de cinco estados se detiene tras 47.176.870 pasos, y el de seis ya no cabe en ninguna notación corriente.
Tibor Radó propuso en 1962 una manera de darle rostro a la incomputabilidad. Tomemos todas las máquinas de Turing con n estados que acaban parándose y preguntémonos cuántos pasos ejecuta la que más tarda. Esa es la función del castor afanoso, y Radó demostró que no es computable y que crece más deprisa que cualquier función que sí lo sea. Los primeros valores son manejables, uno, seis, veintiuno, ciento siete. El quinto se resistió treinta y cinco años.
La máquina campeona la habían encontrado Heiner Marxen y Jürgen Buntrock en 1989, pero demostrar que ninguna otra tarda más exigía clasificar 181.385.789 máquinas distintas. Lo consiguió en julio de 2024 una colaboración abierta de aficionados y matemáticos reunida en el proyecto bbchallenge, y el resultado, 47.176.870 pasos, quedó además formalizado y verificado en el asistente de demostración Coq. Es el primer valor nuevo de la función en más de cuarenta años y el primero de la serie verificado formalmente.
El sexto valor no se conoce y averiguarlo parece extraordinariamente difícil. En junio de 2025 se estableció una cota inferior tan enorme que escribirla explícitamente en notación decimal resulta impracticable, la máquina campeona actual supera \(2 \uparrow\uparrow 2 \uparrow\uparrow 2 \uparrow\uparrow 10\) pasos, donde la doble flecha indica torres de potencias iteradas. El obstáculo tiene nombre propio, Antihydra, una máquina de seis estados cuya parada depende de un problema abierto del tipo Collatz. Determinar el sexto castor exigiría resolver antes esa conjetura. Es lo que ocurre cuando un sistema de reglas mínimas alcanza la universalidad, algo que TecnoTimes ya rozó al escribir sobre el juego de la vida de Conway llevado a los cúbits, seis estados bastan para esconder preguntas que la matemática actual no sabe contestar.
Que un problema sea decidible no significa que se pueda resolver en un tiempo razonable.
La perspectiva de TecnoTimes sobre qué frontera marcó realmente Turing.
Conviene no confundir dos fronteras que se citan juntas y son distintas. La computabilidad pregunta si existe algún algoritmo, con tiempo ilimitado, que resuelva un problema. La complejidad pregunta cuánto tiempo necesita ese algoritmo cuando existe. El problema de la satisfacibilidad booleana es perfectamente decidible, solo que no se sabe resolverlo rápido, y de ahí la pregunta de si P es igual a NP, uno de los siete problemas del milenio del Instituto Clay que sigue abierto en 2026 pese a la cadena constante de demostraciones anunciadas que no superan la revisión. El problema de la parada está en otra categoría, no es que sea lento, es que queda fuera de toda la jerarquía.
Dato TecnoTimes. La máquina de Turing no se inventó para construir ordenadores. Se inventó para demostrar que algo era imposible, y la definición de cómputo mecánico salió como herramienta auxiliar de esa demostración. El ordenador es, en sentido estricto, un subproducto de un resultado negativo.
La lectura de TecnoTimes es que estos teoremas han cambiado de destinatario sin que casi nadie lo note. Durante décadas fueron una curiosidad de los fundamentos, algo que se estudia en segundo de carrera y luego se olvida. Hoy delimitan una promesa concreta que se repite en el debate sobre inteligencia artificial, la de construir un verificador automático que compruebe de forma general que un sistema hace lo que dice hacer. Si la propiedad que se quiere verificar es semántica y no trivial, no existe un procedimiento universal capaz de decidirla para cualquier programa arbitrario. Eso no hace inútil la verificación formal, porque sí pueden demostrarse propiedades concretas sobre sistemas restringidos, modelos específicos o programas acompañados de determinadas hipótesis. Lo que Rice excluye es el verificador general capaz de decidir cualquier propiedad relevante de cualquier programa. Conviene tenerlo presente al leer lo que TecnoTimes escribió sobre la arquitectura del abismo, la automejora y el control corporativo, porque el control prometido tiene un techo matemático anterior a cualquier ordenador.
Referencias.
Fuentes y documentación utilizada.
🧠 DEBATE TECNOTIMES | Los límites de la computación, 2026
¿Se puede prometer control automático sobre sistemas cuyo comportamiento es, por teorema, indecidible?
El teorema de Rice establece que no existe un algoritmo general capaz de decidir cualquier propiedad semántica no trivial para todos los programas posibles. La seguridad informática y el análisis estático conviven con límites de este tipo mediante aproximaciones, restricciones y modelos que permiten obtener respuestas útiles sin pretender resolver el problema general.
La pregunta se ha vuelto actual porque el debate sobre inteligencia artificial recurre a la idea de verificadores capaces de garantizar que un sistema hace lo que declara. Frente a ello puede argumentarse que en la práctica no se verifican programas arbitrarios, sino sistemas concretos, propiedades determinadas y modelos sometidos a restricciones donde sí caben pruebas formales. La cuestión aparece cuando el sistema puede modificar su propio comportamiento, utilizar herramientas externas o actuar fuera de las condiciones bajo las que fue verificado.
- 🧩 ¿Qué garantías de comportamiento se pueden prometer realmente cuando sabemos que no existe un método general capaz de verificar todas las propiedades de cualquier programa?
- 🔐 Si todo antivirus es necesariamente aproximado, ¿qué deberíamos exigirle exactamente a uno, y qué no?
- ⚙️ ¿Sirve de algo restringir el lenguaje o el sistema hasta volverlo verificable, aunque eso limite lo que puede hacer?
- 🚨 ¿Debería enseñarse la indecidibilidad como parte de la alfabetización técnica básica, y no solo en una asignatura de carrera?
