Tio Petros

Viene de aquí

Los números de Ackermann son bastante grandes, pero no son todavía lo suficientemente grandes. La búsqueda por todavía mayores números nos lleva de vuelta a los formalismos. Después de que Ackermann demostrase que `recursiva primitiva’ no es lo que queremos decir con `computable’, la pregunta todavía permanece: ¿Qué queremos decir con `computable’? En 1936, Alonzo Church y Alan Turing respondieron independientemente esta pregunta. Mientras Church respondió utilizando un formalismo lógico llamado el cálculo lambda, Turing respondió utilizando una máquina de cómputo idealizada (la máquina de Turing) que, en esencia, es equivalente a cada Compaq, Dell, Macintosh y Cray del mundo moderno. El artículo de Turing que describía su máquina, "Sobre los números computables", es debidamente celebrado como el documento fundador de la informática.

"Computar," dice Turing,

Turing continúa explicando su máquina utilizando ingeniosos razonamientos desde los primeros principios. La cinta, dice Turing, se extiendo infinitamente en ambas direcciones, para que la máquina teórica no esté restringida por limitaciones físicas de recursos. Además, hay un símbolo escrito en cada cuadrado de la cinta, como el `1’ y el `0’ en la memoria de los ordenadores modernos. Pero ¿cómo son manipulados los símbolos? Bueno, hay un `cabezal’ moviéndose adelante y atrás a lo largo de la cinta, examinando un cuadrado de cada vez, escribiendo y borrando símbolos de acuerdo a reglas definidas. Las reglas están en el programa del cabezal: cámbialos, y cambiarás lo que hace el cabezal.

La augusta perspicacia de Turing fue que podemos programar el cabezal para llevar a cabo cualquier computación. Las máquinas de Turing pueden sumar, multiplicar, extraer raíces cúbicas, ordenar, buscar, comprobar la ortografía, analizar, jugar al tres en raya, listar la sucesión de Ackermann... Si representamos la entrada de datos por el teclado, la salida de datos por la pantalla, y demás como símbolos en la cinta, incluso podríamos ejecutar Windows en una máquina de Turing. Pero hay un problema. Dispón un cabezal sobre una secuencia de símbolos, y eventualmente podría parar, o podría ejecutarse para siempre... como el legendario programador que se queda atrancado en la ducha porque las instrucciones del bote de champú dicen "enjabonar, enjuagar, repetir". Si la máquina va a funcionar por siempre, estaría bien saberlo de antemano, para que no gastemos una eternidad esperando que acabe. Pero ¿cómo podemos determinar, en una cantidad de tiempo finita, si algo va a continuar indefinidamente? Si apuestas con un amigo que tu reloj nunca parará de hacer tic-tac, ¿cuándo declararás victoria? Pero quizá haya algún ingenioso programa que pueda examinar a otros programas y decirnos, infaliblemente, si pararán alguna vez de funcionar. No lo habíamos pensado todavía.

No hay. Turing probó que este problema, llamado el problema de la detención, es irresoluble por las máquinas de Turing. La demostración es un bello ejemplo de autoreferencia. Formaliza un viejo argumento sobre por qué nunca puedes tener una introspección perfecta: porque si pudieses, entonces podrías determinar qué estarías haciendo diez segundos después, y entonces hacer otra cosa distinta. Turing imaginó que hay una máquina especial que podría resolver el problema de la detención. Entonces mostró cómo podemos tener a esta máquina analizándose a sí misma, de tal forma que tiene que parar si se ejecutaría para siempre, y se ejecutaría para siempre si se para. Como un sabueso que finalmente se coge su cola y se devora a sí mismo, la mítica máquina se desvanece en una furia de contradicción. (Que es la clase de cosas que nunca dirías en un artículo de investigación.)

Continua aquí