¿Cómo calcula una máquina, por dentro?

Un modelo de lenguaje que corre en una tarjeta gráfica hace billones de operaciones por segundo, y cada una, en el fondo, está hecha de interruptores que están encendidos o apagados. ¿Cómo se pasa de un interruptor a una máquina que suma, recuerda y sigue un programa? La respuesta tardó un siglo en armarse, del álgebra de George Boole (1854) a los primeros ordenadores con programa almacenado (1948), y es el cimiento sobre el que se apoya todo lo demás de esta web.

La pieza clave salió de una tesis de máster. En 1937 Claude Shannon, con veintiún años, mostró que los circuitos de relés de las centralitas telefónicas obedecen exactamente el álgebra de Boole: un interruptor es una variable que vale $0$ o $1$, dos interruptores en serie son un $\wedge$ (y) y dos en paralelo, un $\vee$ (o). Diseñar un circuito pasó a ser cuestión de manipular fórmulas, y razonar con fórmulas, algo que podía hacer un circuito.

§Basta una puerta

Una función booleana de $n$ entradas es cualquier regla $f:\{0,1{\}}^n\to \{0,1\}$. Hay muchas: cada una de las $2^n$ entradas posibles puede ir a $0$ o a $1$, así que hay $2^{2^n}$ funciones, ya 65 536 para $n=4$. Y sin embargo un puñado de piezas basta para construirlas todas; de hecho, basta una sola: la puerta NAND, «no y».

Demostración

Para cada entrada $a\in \{0,1{\}}^n$ con $f(a)=1$, se forma la conjunción $m_a(x)={\ell }_1\wedge \dots \wedge {\ell }_n$, donde ${\ell }_i=x_i$ si $a_i=1$ y ${\ell }_i=\neg x_i$ si $a_i=0$. Por construcción, $m_a(x)=1$ exactamente cuando $x=a$. Así que

$$f(x)=\underset{a:f(a)=1}{\bigvee }{m}_a(x),$$

que vale $1$ justo en las entradas en que $f$ vale $1$ (si no hay ninguna, $f=x_1\wedge \neg x_1$). Es la forma normal disyuntiva. Para NAND basta con reconstruir las tres puertas:

$$\neg x=\mathrm{NAND}(x,x),x\wedge y=\neg \mathrm{NAND}(x,y),x\vee y=\mathrm{NAND}(\neg x,\neg y),$$

la última por la ley de De Morgan, $\neg (\neg x\wedge \neg y)=x\vee y$.

La demostración construye circuitos que pueden ser enormes, y Shannon probó en 1949 que, para la mayoría de las funciones, no hay remedio: hay $2^{2^n}$ funciones pero muchísimos menos circuitos pequeños, así que casi toda función de $n$ entradas necesita del orden de $2^n/n$ puertas. Las funciones que nos interesan son las raras excepciones con circuitos pequeños. La suma es una de ellas.

§De las puertas a la aritmética

Para sumar dos números en binario se hace lo que se aprende en el colegio: columna a columna, llevándose. En la columna $i$ entran tres bits, $x_i$, $y_i$ y el acarreo $c_i$, y salen dos: la cifra del resultado $s_i$ y el acarreo siguiente $c_{i+1}$. Con $\oplus$ para el o exclusivo (que vale $1$ cuando lo vale exactamente una de sus entradas), el sumador completo es

Demostración

Comprobando las ocho entradas posibles se ve que el sumador completo escribe en binario la suma de sus tres bits: $x_i+y_i+c_i=s_i+2c_{i+1}$. Multiplicando por $2^i$ y sumando en $i$,

$$x+y=\sum _i(x_i+y_i)2^i=\sum _i(s_i+2c_{i+1}-c_i)2^i=\sum _i{s}_i{2}^i+\sum _i(c_{i+1}{2}^{i+1}-c_i{2}^i),$$

y la última suma es telescópica: vale $c_n{2}^n-c_0=c_n{2}^n$.

Cada sumador completo cuesta cinco puertas (o nueve puertas NAND), así que sumar números de 64 bits lleva unos cientos de puertas. Multiplicar, comparar o calcular un $\mathrm{softmax}$ es cuestión de más circuitos del mismo tipo. Lo que aún falta es la memoria.

§La memoria, y los autómatas finitos

Un circuito cuya salida vuelve a su entrada puede recordar. Dos puertas NAND conectadas en bucle forman un biestable que guarda un bit hasta que se le ordena cambiarlo. Con $k$ de esos bits y un reloj que marca el paso, un circuito tiene $2^k$ estados posibles y, en cada tic, pasa de un estado a otro según el estado y lo que entra. Ese objeto, quitada la electrónica, es un autómata finito.

La idea vino de un sitio inesperado: el modelo de neuronas de McCulloch y Pitts (1943), redes de unidades con umbral que Stephen Kleene analizó en 1951 para preguntarse qué «sucesos» podían detectar. La respuesta, los lenguajes que reconocen los autómatas finitos, tiene además una descripción muy concreta.

Una expresión regular describe un conjunto de palabras con tres operaciones: unión ($r\mid s$, una u otra), concatenación ($rs$, una detrás de otra) y la estrella de Kleene ($r^{\ast }$, cualquier número de repeticiones). Por ejemplo, $(0\mid 1{)}^{\ast }01$ es «cualquier palabra que termine en $01$».

Para pasar de expresiones a autómatas conviene dejar que el autómata adivine. Un autómata no determinista (AFN) puede tener varias transiciones con el mismo símbolo, o ninguna, y acepta si alguna elección lleva a un estado de aceptación. Cada operación de una expresión se convierte entonces en una pequeña pieza de AFN (la construcción de Thompson, de 1968, todavía en el corazón de muchos motores de expresiones regulares). Adivinar parece dar más poder. No lo da:

Demostración

El AFD lleva la cuenta de todos los estados en que podría estar el AFN. Sus estados son los subconjuntos $S\subseteq Q$; empieza en $\{q_0\}$; al leer $a$ pasa a ${\delta }^{\prime }(S,a)=\bigcup _{q\in S}\delta (q,a)$; y acepta si $S\cap F\ne \varnothing$. Por inducción en la longitud de la palabra, tras leer $w$ el AFD está exactamente en el conjunto de estados a los que el AFN puede llegar con $w$, así que acepta si y solo si lo hace alguna ejecución del AFN. Hay $2^n$ subconjuntos.

La exponencial es real: el lenguaje «el $n$-ésimo símbolo empezando por el final es un $1$» tiene un AFN con $n+1$ estados, y todo AFD para él necesita al menos $2^n$. Rabin y Scott recibieron el premio Turing en 1976 por este artículo, que además introdujo el no determinismo, una idea que una década después estaría en la base de la pregunta $\mathrm{P}$ frente a $\mathrm{NP}$.

§Lo que no puede hacer la memoria finita

El autómata de la figura no se puede ampliar para reconocer $a^n{b}^n$ para todo $n$, por muchos estados que le demos. No es falta de ingenio: es un teorema.

Demostración

Sea $p$ el número de estados de un AFD para $L$. Al leer los $p$ primeros símbolos de $w$, el autómata pasa por $p+1$ estados, así que por el principio del palomar repite alguno: hay posiciones $j<k\le p$ con $q_j=q_k$. Sea $x$ los $j$ primeros símbolos, $y$ los $k-j$ siguientes y $z$ el resto. Leer $y$ lleva al autómata de $q_j$ al mismo estado, así que puede hacerlo cero veces o cien, y acabará donde acababa con $w$: en un estado de aceptación.

Toma $L=\{a^n{b}^n:n\ge 0\}$ y supón que fuera regular, con constante $p$. La palabra $a^p{b}^p$ está en $L$ y, como $\left|xy\right|\le p$, el trozo $y$ está formado solo por aes. Al bombearlo, $x{y}^{2}z$ tiene más aes que bes, y no está en $L$. Contradicción. Un autómata finito no puede contar sin límite: para comprobar que hay tantas bes como aes tendría que recordar un número que puede ser arbitrariamente grande.

§La jerarquía de Chomsky

En 1956 el lingüista Noam Chomsky se preguntó qué tipo de gramática podría describir una lengua humana, y en 1959 ya había ordenado los lenguajes formales en cuatro niveles. Cada tipo de gramática corresponde exactamente a un tipo de máquina, que solo se distinguen por su memoria:

Tipo	Gramática	Máquina	Memoria	Ejemplo que no está en el nivel anterior
3	Regular	Autómata finito	Finita	$(0\mid 1{)}^{\ast }01$
2	Independiente del contexto	Autómata con pila	Una pila	$a^n{b}^n$
1	Dependiente del contexto	Autómata linealmente acotado	Una cinta tan larga como la entrada	$a^n{b}^n{c}^n$
0	Sin restricciones	Máquina de Turing	Una cinta ilimitada	El problema de la parada

Para $a^n{b}^n$ basta una pila: se apila una ficha por cada $a$ y se desapila una por cada $b$. Las gramáticas independientes del contexto, escritas en la notación de Backus–Naur de ALGOL 60, describen la sintaxis de casi todos los lenguajes de programación, y por eso todo compilador empieza con un autómata finito que trocea el texto en símbolos y un autómata con pila que construye el árbol sintáctico. Las lenguas humanas resultaron más escurridizas: algunas construcciones, como las dependencias cruzadas del alemán de Suiza, quedan fuera de las gramáticas independientes del contexto. Sesenta años después, los modelos que mejor predicen el lenguaje no son gramáticas en absoluto, pero eso es otro capítulo.

§La máquina de debajo

Con sumadores, memoria y un autómata finito que los coordine se puede construir un ordenador. En 1945 John von Neumann describió el diseño del EDVAC: una memoria que guarda a la vez los datos y el programa, una unidad que hace la aritmética y una unidad de control que repite siempre el mismo ciclo. El 21 de junio de 1948 el «Baby» de Mánchester fue el primer ordenador que ejecutó un programa guardado en su propia memoria.

1. Buscar: leer de la memoria la instrucción a la que apunta el contador de programa, y avanzar el contador.
2. Decodificar: el autómata de control averigua qué operación es y a qué celda de memoria se refiere.
3. Ejecutar: el sumador o la memoria hacen el trabajo, y el ciclo vuelve a empezar.

Un ordenador real es, en sentido estricto, un autómata finito: con $k$ bits de memoria tiene como mucho $2^k$ estados. Pero con 16 gigabytes, $k$ es del orden de $1,4\times {10}^{11}$, y $2^k$ es un número que nada en el universo puede enumerar. Tiene más sentido pensar en la memoria como una cinta que siempre se puede alargar. Esa idealización, la cinta infinita, es exactamente la máquina de Turing.

§Referencias

1. G. Boole (1854). An Investigation of the Laws of Thought. Walton and Maberly.
2. C. E. Shannon (1938). «A Symbolic Analysis of Relay and Switching Circuits». Transactions of the AIEE, 57(12).
3. W. S. McCulloch y W. Pitts (1943). «A Logical Calculus of the Ideas Immanent in Nervous Activity». Bulletin of Mathematical Biophysics, 5.
4. J. von Neumann (1945). First Draft of a Report on the EDVAC.
5. C. E. Shannon (1949). «The Synthesis of Two-Terminal Switching Circuits». Bell System Technical Journal, 28(1).
6. S. C. Kleene (1956). «Representation of Events in Nerve Nets and Finite Automata». En Automata Studies, Princeton University Press.
7. N. Chomsky (1956). «Three Models for the Description of Language». IRE Transactions on Information Theory, 2(3).
8. N. Chomsky (1959). «On Certain Formal Properties of Grammars». Information and Control, 2(2).
9. M. O. Rabin y D. Scott (1959). «Finite Automata and Their Decision Problems». IBM Journal of Research and Development, 3(2).
10. Y. Bar-Hillel, M. Perles y E. Shamir (1961). «On Formal Properties of Simple Phrase Structure Grammars». Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14.
11. K. Thompson (1968). «Regular Expression Search Algorithm». Communications of the ACM, 11(6).
12. J. E. Hopcroft, R. Motwani y J. D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation, 3.ª ed. Addison-Wesley.