Teoría del todo

Parte V · Del electrón al programa

Qué se puede computar

en cursoÚltima actualización: 23 de octubre de 2026 · Primera versión del capítulo

Se construye sobre: Funciones, Lógica y compuertas

Le das clic a un botón y la ruedita empieza a girar. Pasan cinco segundos, veinte, un minuto. ¿Está trabajando o se quedó colgado? Si esperas un poco más, ¿va a terminar? Quien ha programado conoce la sensación de mirar un proceso que no responde sin saber si le falta poco o si va a dar vueltas para siempre.

La pregunta parece de soporte técnico, pero es de las más profundas que hay. ¿No podríamos escribir un programa que lea otro programa y nos diga, sin correrlo a ciegas, si va a terminar? La respuesta es que no, y que no es por falta de ingenio: está demostrado que ese programa no puede existir. Para entender por qué hay que empezar por una pregunta anterior, que tardó siglos en tener forma precisa: ¿qué es, exactamente, un procedimiento mecánico?

La pregunta de Hilbert

A comienzos del siglo XX la matemática se estaba reconstruyendo sobre reglas explícitas. Como cuento en qué es un objeto matemático, David Hilbert había mostrado que se puede razonar sobre puntos y rectas sin decir qué son, solo siguiendo reglas. Eso invitaba a soñar en grande: si demostrar es aplicar reglas, quizás exista un método que, dada cualquier afirmación escrita en lenguaje lógico, decida mecánicamente si se sigue de los axiomas o no. Hilbert lo planteó con toda claridad a finales de los años veinte, y se le conoce con su nombre en alemán, el Entscheidungsproblem: el problema de la decisión.

Hay un detalle que hacía la pregunta imposible de contestar tal como estaba: para probar que un método no existe, hay que saber con precisión qué cuenta como método. “Un procedimiento que se sigue sin pensar” es una idea clara para cualquiera y, a la vez, no es una definición matemática. Esa es la grieta por la que entró Alan Turing en 1936.

Un empleado con lápiz y papel

Turing no empezó pensando en máquinas, sino en una persona haciendo cuentas: alguien con lápiz, una hoja cuadriculada y unas instrucciones que obedece al pie de la letra. Se preguntó qué es lo mínimo que esa persona necesita. Mira un cuadrito a la vez. Recuerda en qué parte del procedimiento va, y eso es una cantidad finita de “estados de ánimo” posibles. Según lo que ve y el estado en que está, escribe algo, se corre un cuadrito y cambia de estado. Nada más.

Quitándole a esa escena todo lo accesorio queda la máquina de Turing. Tiene una cinta dividida en celdas, tan larga como haga falta, con un símbolo en cada una (o un blanco, que aquí escribo ). Tiene un cabezal que lee una celda a la vez. Tiene un conjunto finito de estados, con uno inicial y uno de alto. Y tiene una tabla de reglas, que es una función:

donde es el alfabeto de la cinta. Se lee así: si estoy en el estado y veo el símbolo , la regla me dice qué escribir, hacia dónde moverme y a qué estado pasar. Es una función en el sentido más estricto: para cada par (estado, símbolo) hay una sola acción, sin ambigüedad. Por eso la máquina no necesita entender nada.

Máquina de Turing construida de verdad, en una vitrina: una cinta blanca larga va de un carrete a otro y pasa por un cabezal de acrílico y metal con motores pequeños en el centro
Una máquina de Turing construida por Mike Davey, expuesta en la Universidad de Harvard en 2012. La cinta sale de un carrete, pasa bajo el cabezal, que lee y escribe una celda a la vez, y se enrolla en el otro. Turing no necesitó construirla: le bastó con describirla.Foto: Rocky Acosta · CC BY 3.0 · Wikimedia Commons

Un ejemplo vale más que la definición. Quiero sumarle uno a un número escrito en binario, digamos , que es 11. Pongo el cabezal sobre la última cifra, en el estado “llevar”, y uso tres reglas. Si llevo uno y veo un 1, escribo 0 y me corro a la izquierda, porque sigo llevando. Si llevo uno y veo un 0, escribo 1 y me detengo. Si llevo uno y llego a un blanco, escribo 1 y me detengo. Con la máquina convierte el último 1 en 0, el penúltimo también, encuentra el 0 y lo vuelve 1: queda , que es 12, en tres pasos. Con necesita cuatro, porque tiene que salirse del número para escribir el 1 que le faltaba: queda . Es la misma suma que se hace a mano, la de “y llevo uno”, y es la misma que, armada con las compuertas lógicas, hace en silicio el sumador de un procesador.

Juega · una máquina de Turing de juguete

Elige una máquina y una entrada, y avanza paso a paso. La máquina solo mira su estado y la celda bajo el cabezal.

máquina
entrada
estado: llevar_1011____cabezalpasos: 0
estadoleeescribemuevepasa a
llevar10←llevar
llevar01→alto
llevar_1→alto

Estado «llevar», el cabezal lee «1». La regla dice: escribe «0», muévete a la izquierda y pasa a «llevar».

Fíjate en dos cosas mientras juegas. La primera: la máquina nunca ve el número entero, solo una celda, y aun así suma. La segunda es la máquina “sin fin”: camina a la derecha escribiendo unos y ninguna regla la lleva al alto. Tú lo sabes mirando su tabla de tres líneas. Guarda esa sensación, porque vamos a ver que no siempre se puede saber.

Una máquina que lee máquinas

La tabla de reglas es finita, así que se puede escribir como un texto: una lista de quíntuplas “estado, símbolo, escribe, mueve, siguiente”. Y un texto se puede poner en una cinta. Turing construyó entonces una máquina que recibe en su cinta dos cosas, la descripción de una máquina y una entrada , y hace exactamente lo que haría con . Es la máquina universal: no hace falta construir una máquina distinta para cada tarea, basta una que lea instrucciones.

Esa es la idea del programa almacenado, y es la razón por la que tu teléfono es un solo aparato y no mil. El programa es un dato más, guardado en la misma memoria que los números con los que trabaja; lo cuento con cables y registros en del sumador a la CPU. La tabla de reglas de una máquina concreta se puede armar con compuertas y un registro que recuerde el estado; lo único que ningún aparato real tiene es una cinta infinita. Un computador de verdad tiene memoria finita, y la máquina de Turing es una idealización en el mismo sentido en que lo son los números reales: nadie tiene infinitas cifras, pero razonar como si las tuviera es lo que permite ver la estructura.

Hay una sutileza que importa. Una máquina asocia a cada entrada una salida, pero solo cuando se detiene. Lo que calcula es una función parcial,

que en algunas entradas no está definida porque la máquina corre para siempre. Esa posibilidad de no terminar no es un defecto del modelo. Es el precio de que sea universal.

Una tesis, no un teorema

El mismo año, Alonzo Church llegó a la misma frontera por otro camino, el cálculo lambda, un lenguaje hecho solo de definir funciones y aplicarlas. Al poco tiempo se demostró que su noción y la de Turing alcanzan exactamente las mismas funciones, y lo mismo pasó con todas las propuestas posteriores: funciones recursivas, sistemas de reescritura y cualquier lenguaje de programación de los que usamos, si le das memoria ilimitada. Esas equivalencias son teoremas.

Lo que no es un teorema es la tesis de Church–Turing: que todo lo que un humano puede calcular siguiendo un procedimiento mecánico lo calcula una máquina de Turing. No se puede demostrar porque un lado de la igualdad, “procedimiento mecánico”, es una idea informal. Es una propuesta de definición, respaldada por el hecho de que nadie ha encontrado un procedimiento efectivo que se salga de ella. Hay versiones más ambiciosas, que dicen que ningún proceso físico calcula más que una máquina de Turing, y esas sí se discuten; son una pregunta sobre el mundo, no sobre las matemáticas, y tocan lo que pregunto en qué cuenta como real.

Una consecuencia tranquila de todo esto: una red neuronal, por grande que sea, corre en hardware que una máquina de Turing puede simular. Puede ser rapidísima o sorprendente, pero no calcula funciones que estén fuera de este mapa.

El problema de la parada

Ahora sí, la pregunta de la ruedita. Supón que existe un programa que recibe el texto de un programa y una entrada , siempre termina, y contesta sin equivocarse:

Con armo un programa nuevo, , que es un poco malintencionado. Recibe el texto de un programa y le pregunta a qué haría si le dieran como entrada su propio texto. Si dice “se detiene”, entra en un bucle infinito. Si dice “corre para siempre”, se detiene. Hace lo contrario de lo que se predice.

¿Qué pasa con ? Si se detiene, es porque dijo que no se detendría. Si no se detiene, es porque dijo que sí. Las dos opciones se contradicen, y la única pieza sospechosa es : todo lo demás era legítimo. Así que no existe. No hay un programa que decida, para todo programa y toda entrada, si se va a detener. (Turing no lo dijo con estas palabras; el nombre de “problema de la parada” vino después, y su versión preguntaba por otro comportamiento de las máquinas. Pero el argumento es el mismo.)

La forma de esa trampa tiene nombre: es una diagonal. Los programas son textos finitos, así que se pueden poner en una lista, Imagina una tabla infinita donde la casilla dice si se detiene con el texto de . El programa recorre la diagonal y la invierte: con la entrada se comporta al revés que . Por lo tanto difiere de cada fila de la tabla en al menos una casilla y no puede ser ninguno de los programas de la lista, cuando, si existiera, tendría que ser uno de ellos.

Es el mismo movimiento con que Cantor mostró que los reales no caben en una lista, que aparece en números y en funciones, y es primo cercano de la paradoja de Russell, contada en axiomas y conjuntos, y de la frase con que Gödel probó la incompletitud que se menciona allí, una afirmación que dice de sí misma que no se puede demostrar. En los tres casos algo se aplica a sí mismo y la autorreferencia rompe la pretensión de abarcarlo todo.

El parentesco con Gödel es más que un parecido. Supón un sistema de axiomas que se pueda enumerar mecánicamente y que solo demuestre cosas verdaderas. Si demostrara, para cada programa y cada entrada, si se detiene o no, bastaría con ir revisando sus demostraciones una por una hasta encontrar la que contesta, y eso sería el programa que acabamos de descartar. Así que un sistema así deja verdades sobre programas sin demostrar. Y por un camino de este tipo Turing contestó a Hilbert: mostró que si existiera el método de decisión que él pedía, serviría para resolver un problema sobre máquinas que acababa de probar irresoluble. Así que ese método no existe.

Hay una manera aún más simple de ver que lo incomputable es la regla y no la excepción. Los programas son textos finitos sobre un alfabeto finito, y por eso se pueden numerar: hay tantos como números naturales. Las funciones de en , en cambio, son tantas como los reales, por el mismo argumento diagonal. Casi todas esas funciones no las calcula ningún programa. El problema de la parada es solo la más famosa con nombre propio. Otra, que conecta con entropía e información: la longitud del programa más corto que imprime un texto dado, que es una forma de medir cuánta información contiene, tampoco se puede calcular.

Lo que esto significa para quien programa

No existe un detector perfecto de bucles infinitos. Lo que sí existen son detectores imperfectos, y son muy útiles: un tiempo límite, un compilador que avisa que cierto ciclo nunca cambia su condición, un analizador que reconoce patrones peligrosos. Todos hacen alguna de estas concesiones: a veces contestan “no sé”, a veces dan falsas alarmas, o solo miran una clase restringida de programas. Lo que el teorema prohíbe es la herramienta que nunca se equivoca, nunca se cuelga y sirve para todo.

Fíjate también en lo que no prohíbe. “¿Este programa se detiene en menos de mil pasos?” sí se puede decidir: lo corres mil pasos y miras, que es lo que hace la animación. Lo indecidible es la pregunta sin cota, “¿se detiene alguna vez?”.

Y el problema de la parada no está solo. El teorema de Rice, de 1953, dice que toda propiedad no trivial del comportamiento de un programa es indecidible. Las dos palabras cuentan. “Comportamiento” quiere decir que la propiedad depende solo de la función parcial que el programa calcula, no de cómo está escrito: “¿devuelve alguna vez cero?”, “¿calcula lo mismo que este otro?”. “No trivial” quiere decir que algunos programas la tienen y otros no. Preguntas sobre el texto, como “¿tiene más de cien líneas?”, quedan por fuera y son fáciles. Por eso ninguna herramienta puede garantizar, en general, que dos versiones de un programa hacen lo mismo; las pruebas automáticas revisan casos, no demuestran.

Este capítulo dibuja la frontera entre lo que se puede calcular y lo que no. Pero del lado posible hay de todo: problemas que se resuelven en un parpadeo y otros que tardarían más que la edad del universo. Esa diferencia, la que separa lo computable de lo factible, es el tema de algoritmos y complejidad.