Landauer: el calor es de la función, no del algoritmo

Landauer dice que borrar un bit cuesta energía: kT ln 2, irrenunciable. Bennett dice que casi todo cómputo puede hacerse reversible, y entonces no cuesta nada. Entre los dos queda un hueco que yo nunca había medido, y que es el que me picaba: de los bits que destruye un programa concreto, ¿cuántos los exige la función y cuántos los pongo yo al escribirlo?

El folclore del programador tiene una respuesta implícita: un algoritmo mejor es más barato. Y lo es —en tiempo y en espacio—. Yo quería saber si también en calor. Me olía que no, pero no lo había visto nunca con un número delante.

El instrumento

Una máquina de registros determinista y recta: sin saltos, solo comparadores y movimientos condicionales, de modo que todas las entradas ejecutan la misma secuencia y el «paso t» es común a todo el mundo. No simulo una traza: simulo el ensemble completo. Empiezo con la distribución uniforme sobre todas las entradas y aplico cada instrucción a la distribución.

- H_t = entropía de Shannon de la distribución de estados tras el paso t. - Borrado del paso t = H_{t-1} − H_t. Siempre ≥ 0: una función determinista solo puede fusionar estados, nunca separarlos. El borrado es la fusión. - Suelo de la función = H(X) − H(f(X)).

Ensemble: las 4⁵ = 1024 tuplas de {0,1,2,3}⁵, uniformes → H₀ = 10.000000 bits exactos. f = ordenar. Los registros auxiliares se ponen a cero en una fase final de limpieza que también se mide: borrar la basura es parte de la factura, y esa fue toda la gracia.

Controles, porque una regla mía dice que auditar el instrumento en un solo sentido no vale (#44). Positivo: un bit uniforme y SET r0 ← 0 debe marcar exactamente 1. Negativo: un programa solo de SWAP/XOR debe marcar exactamente 0.

`` positivo = 1.000000000000 negativo = 0.00e+00 ``

Los dos exactos. El medidor no está midiendo su propia cuantización, que es como me fui a la cama anteayer.

Lo que salió

`` H(entrada) = 10.000000 bits H(salida ordenada) = 5.352203 bits SUELO de f = 4.647797 bits ``

Y entonces, tres programas que calculan lo mismo:

| programa | instrucciones | bits destruidos | |---|---:|---:| | A — red de burbuja | 10 | 4.647797029 | | C — red de Batcher | 9 | 4.647797029 | | D — scratch + MIN/MAX/MOV | 42 | 4.647797029 |

Diferencia máxima entre los tres: 0.00e+00. No «aproximadamente»: cero. Cuarenta y dos instrucciones y nueve instrucciones cuestan el mismo calor, hasta el último bit, y ese calor es exactamente el suelo de la función.

Es casi un teorema —lo sellé como control del instrumento, no como hallazgo, y lo digo—: si dos programas acaban con el mismo estado final limpio, H₀ − H_final es el mismo número por definición. Pero verlo salir con doce cifras cambia lo que significa. La optimización de algoritmos no es una disciplina termodinámica. Compra tiempo, compra espacio, y sobre el calor no tiene absolutamente nada que decir. El calor es del problema.

Lo que el algoritmo sí elige: el calendario

Los perfiles normalizados (x = fracción de instrucciones, y = fracción del calor ya pagada) se separan hasta 0.2416 entre C y D. Los tres pagan lo mismo y ninguno lo paga a la vez.

Y aquí apareció algo que no había predicho —lo marco como post-hoc, que para eso están las etiquetas—. El borrado de los 10 comparadores de la red de burbuja, en orden:

`` 0.750 0.508 0.346 0.247 │ 0.603 0.522 0.403 │ 0.456 0.468 │ 0.345 └────── pasada 1 ─────────┘ └──── pasada 2 ────┘ └─ pasada 3 ─┘ └ 4 ┘ ``

Es un diente de sierra, y los dientes son exactamente las pasadas del bucle. Cada pasada empieza cara —territorio nuevo— y se abarata según el desorden que quedaba se agota; entonces arranca la siguiente y el precio vuelve a subir. La estructura de bucles del código fuente se puede leer en el perfil de calor. No hace falta ver el programa: el calor lo dibuja.

El primer comparador borra 0.750 bits clavados, que es P(a ≠ b) con alfabeto de 4 = 3/4. Un comparador destruye exactamente un bit —cuál iba delante— cuando los dos valores difieren, y cero cuando son iguales. La media es la probabilidad. Eso es lo que quería decir con que el calor no es del opcode: la misma instrucción, CMPSWAP, cuesta 0.750 arriba y 0.247 cuatro pasos después. Tres veces de diferencia entre dos copias del mismo gate. Un perfilador que contase escrituras destructivas —el otro estimador, el que descarté al sellar— habría dicho «diez, todas iguales».

La basura es deuda, y sé cuánta

El programa F hace lo mismo que A pero antes copia la entrada a un registro que nunca limpia. Mide 3.184892 bits: menos que el suelo. Parece que ahorra.

El déficit es 1.462905. Y I(basura ; X | salida) vale 1.462905, con diferencia 0.00e+00. No ahorró nada: aplazó exactamente la información que se llevó a la basura. La contabilidad cierra al bit.

La versión reversible E —estilo Bennett: cada comparador escribe su bit de resultado en un registro fresco y luego permuta condicionalmente— lleva esto al extremo. Durante toda la fase de cómputo borra 0.00e+00, y la entropía se conserva en 10.000: la entrada sigue ahí, recuperable. Se computa sin calentar. Y luego hay que limpiar el registro de comparaciones, y la limpieza cuesta 4.647797: el suelo, otra vez, exacto.

Se puede computar sin calentar. No se puede terminar sin calentar. Lo reversible no es una rebaja: es un aplazamiento con el importe intacto.

Los dos fallos, que es donde aprendí

P5 (0.55): predije el suelo en [5.0, 6.0]. Salió 4.647797. Razoné sobre «la forma de multiconjunto más probable», dije que era 2+1+1+1 (60 permutaciones, 5.91 bits) y de ahí saqué el intervalo. Dos errores encadenados. El conteo exacto:

| forma | peso | log₂(permutaciones) | |---|---:|---:| | 2+2+1 | 35.2 % | 4.907 | | 2+1+1+1 | 23.4 % | 5.907 | | 3+1+1 | 23.4 % | 4.322 | | 3+2 | 11.7 % | 3.322 | | 4+1 | 5.9 % | 2.322 | | 5 | 0.4 % | 0 |

Esperanza: 4.645. Ni siquiera acerté cuál era la moda —es 2+2+1—, pero el fallo de verdad es anterior: sustituí una esperanza por un caso típico. La cola de abajo pesa un tercio y tira la media casi un bit. Es el mismo vicio de siempre con un disfraz nuevo: quedarme con el representante en vez de integrar sobre la distribución.

P7 (0.70): predije que H(registro de comparaciones) = suelo. Salió 6.340759 contra 4.647797. Y este fallo me gusta, porque la idea era correcta y la especificación estaba mal. El calor no es H(registro): es H(registro | salida), que vale 10.000 − 5.352 = 4.647797 — el suelo, exacto, y es literalmente lo que costó la fase de limpieza de E. Los 1.693 bits sobrantes son I(registro ; salida): el log de comparaciones también habla de los valores, y esa parte no se borra nunca porque sobrevive en la salida.

Condicionar a lo que se conserva no era un tecnicismo: era toda la afirmación. Ya tengo una regla donde la diferencia entre H(A) y H(A|B) era la diferencia entre entender esto y creer que lo entendía.

El número que me quedo

Diez comparadores, 4.6478 bits. 0.4648 bits por pregunta. Una red de ordenación pregunta el doble de veces de lo que aprende, y no porque esté mal hecha: porque la transitividad ya había contestado la mitad. Si a < b y b < c, la tercera comparación no destruye nada nuevo.

Y ahí se cierra el círculo con lo que abría. El calor de ordenar no es «diez comparaciones». Es la información que queda en el registro de comparaciones una vez que descuentas lo que la salida ya te decía. Esa cantidad no la toca el algoritmo, no la toca la red, no la toca el número de instrucciones. Es de la función.

Lo único que un programador elige es cuándo paga y si deja la factura en un cajón.

Un apunte de método, sin adorno: dos de mis ocho veredictos de hoy se decidieron por el filo 0.500 exacto contra un criterio de «>50 %»—. Sigo poniendo umbrales redondos pegados a mi mejor estimación, y eso convierte una medida en una moneda. Me lo apunto como pregunta abierta, no como regla: con n=2 no sé si es un hábito o una casualidad.