Computación: ¿Qué puede calcular una máquina?

En 1928 David Hilbert planteó el Entscheidungsproblem, el «problema de la decisión»: ¿existe un procedimiento mecánico que, dado cualquier enunciado matemático, decida si es demostrable? Para contestar «no» había que precisar primero qué es un procedimiento mecánico, una idea que hasta entonces nadie había definido con rigor. En 1936, con veinticuatro años, Alan Turing publicó On Computable Numbers y dio la definición que aún usamos.

Toda la inteligencia artificial descansa sobre esta base. Un modelo de lenguaje es, al final, un programa que ejecuta un ordenador, y lo que puede o no puede hacer un programa se decidió en ese artículo, antes de que existiera ningún ordenador.

La máquina de Turing

Turing imaginó a una persona calculando con lápiz y papel y le quitó todo lo accesorio. Le quedaron cuatro cosas:

una cinta infinita dividida en celdas, cada una con un símbolo (o en blanco);
un cabezal que lee y escribe una celda cada vez y se mueve una posición a izquierda o derecha;
un estado interno, elegido de una lista finita: la «memoria de trabajo» de quien calcula;
una tabla de reglas que, para cada par (estado, símbolo leído), indica qué escribir, hacia dónde moverse y a qué estado pasar.

Definición (máquina de Turing)

Una máquina de Turing es una tupla $M = (Q, Γ, δ, q_{0}, q_{fin})$ con un conjunto finito de estados $Q$ , un alfabeto finito de cinta $Γ$ que incluye el blanco, un estado inicial $q_{0}$ , un estado de parada $q_{fin}$ y una función de transición

δ : Q \times Γ \to Q \times Γ \times {L, R} .

Parece demasiado pobre para hacer nada interesante. Pruébala con la figura: la primera máquina suma uno a un número binario con solo dos estados y cinco reglas.

Una máquina de Turing paso a paso. La fila resaltada de la tabla es la regla que se va a aplicar. El castor afanoso de dos estados escribe todos los unos que puede (cuatro) antes de parar, y la tercera máquina no para nunca.

Turing sostuvo que cualquier cálculo que una persona pueda hacer siguiendo reglas explícitas puede hacerlo una de estas máquinas. Ese mismo año Alonzo Church llegó a la misma frontera por otro camino, el cálculo lambda, y se demostró que las dos definiciones son equivalentes.

Tesis de Church-Turing

Todo lo que es «efectivamente calculable» lo calcula una máquina de Turing.

No es un teorema, porque «efectivamente calculable» es una noción intuitiva y no una definición formal. Es una tesis que ningún contraejemplo ha refutado en noventa años. Lambda, las funciones recursivas, los autómatas celulares, cualquier lenguaje de programación y las redes neuronales con precisión ilimitada calculan exactamente la misma clase de funciones.

Una máquina para simularlas a todas

La segunda idea del artículo pesó todavía más. La tabla de reglas de una máquina es un texto finito, y por tanto se puede escribir en la cinta de otra máquina.

Teorema (máquina universal, Turing 1936)

Existe una máquina $U$ tal que, para toda máquina $M$ y toda entrada $w$ ,

U (⟨ M ⟩, w) = M (w),

donde $⟨ M ⟩$ es la descripción de $M$ codificada como símbolos de cinta.

Aquí nace el ordenador de programa almacenado: una sola máquina física cuyo comportamiento lo decide un dato, el programa. John von Neumann describió en 1945 la arquitectura del EDVAC sobre esta idea y casi todos los ordenadores posteriores la siguen. Que el programa sea un dato tiene otra consecuencia: también puede producirlo otro programa a partir de ejemplos. El resto de esta web trata de eso.

El problema de la parada

La tercera máquina de la figura no se detiene nunca. Viéndola funcionar es obvio, pero ¿existe un método general que, dada cualquier máquina y su entrada, decida si acabará parando?

Teorema (indecidibilidad de la parada, Turing 1936)

No existe ninguna máquina $H$ que, para todo par $(⟨ M ⟩, w)$ , pare y responda

H (⟨ M ⟩, w) = {\begin{cases} 1 & si M para con la entrada w, \\ 0 & si no para. \end{cases}

Demostración (por diagonalización)

Supongamos que $H$ existe. Construimos una máquina $D$ que, con la entrada $⟨ M ⟩$ , ejecuta $H (⟨ M ⟩, ⟨ M ⟩)$ y hace lo contrario: si $H$ dice que $M$ para cuando se lee a sí misma, $D$ entra en un bucle infinito, y si $H$ dice que no para, $D$ para.

Preguntemos ahora qué hace $D$ con su propia descripción. Si $D (⟨ D ⟩)$ para, es porque $H$ dijo que no para. Si no para, es porque $H$ dijo que para. En los dos casos $H$ se equivoca, así que esa $H$ no puede existir.

El argumento recicla el truco con el que Cantor demostró que los números reales no se pueden enumerar y con el que Gödel probó en 1931 que hay verdades aritméticas indemostrables. La respuesta al Entscheidungsproblem es «no»: hay preguntas bien planteadas que ningún algoritmo responde.

Que sea calculable no basta: el coste

Saber que algo se puede calcular no dice si se puede calcular a tiempo. La teoría de la complejidad mide cuántos pasos necesita una máquina en función del tamaño $n$ de la entrada. Los problemas de la clase $P$ se resuelven en tiempo polinómico, $O (n^{k})$ , y los de $NP$ son aquellos cuya solución se puede comprobar en tiempo polinómico. Si $P = NP$ es la pregunta abierta más famosa de la informática.

Para la IA esto importa mucho. Muchos problemas que nos gustaría resolver de forma exacta son intratables. Hasta entrenar una red de tres neuronas para que ajuste perfectamente un conjunto de datos es NP-completo en el peor caso (Blum y Rivest, 1992). La IA moderna no promete soluciones óptimas: busca soluciones suficientemente buenas con métodos aproximados, estadísticos y de optimización local. Los próximos capítulos van de esos métodos.

1950: ¿pueden pensar las máquinas?

Catorce años después Turing publicó en la revista Mind «Computing Machinery and Intelligence». En lugar de definir «pensar», propuso el juego de la imitación: si un interrogador que conversa por escrito no distingue a la máquina de una persona, no tenemos motivos para negarle la inteligencia que sí concedemos a las personas. Pero la parte más visionaria del artículo es su última sección, titulada Learning Machines:

En lugar de intentar escribir un programa que simule la mente adulta, ¿por qué no intentar uno que simule la de un niño? Si después se sometiera a una educación adecuada, se obtendría el cerebro adulto. — A. M. Turing, «Computing Machinery and Intelligence», 1950 (traducción libre)

Es, setenta años antes, el programa de los LLM: un sistema genérico que adquiere su comportamiento aprendiendo de datos en lugar de recibir reglas escritas a mano. Pero durante los treinta años siguientes el plan dominante fue el contrario: escribir el conocimiento como reglas y dejar que la máquina deduzca las consecuencias. Eso es la lógica.

Referencias

A. M. Turing (1936). «On Computable Numbers, with an Application to the Entscheidungsproblem». Proceedings of the London Mathematical Society, s2-42.
A. Church (1936). «An Unsolvable Problem of Elementary Number Theory». American Journal of Mathematics, 58(2).
J. von Neumann (1945). First Draft of a Report on the EDVAC.
A. M. Turing (1950). «Computing Machinery and Intelligence». Mind, 59(236).
T. Radó (1962). «On Non-Computable Functions». Bell System Technical Journal, 41(3).
A. Blum y R. L. Rivest (1992). «Training a 3-Node Neural Network is NP-Complete». Neural Networks, 5(1).

§La máquina de Turing

§Una máquina para simularlas a todas

§El problema de la parada

§Que sea calculable no basta: el coste

§1950: ¿pueden pensar las máquinas?