Programas autorreplicantes que emergen del ruido aleatorio

Traducción automática del original en inglés, todavía sin revisar. Leer el original.

La mayoría de los programadores piensa que la Turing completitud (Turing completeness) es el umbral interesante para un sistema computacional. Se lleva toda la atención. Pero hay un umbral más bajo y más raro que importa más para el origen del comportamiento complejo: la autorreplicación.

Un paper reciente de Agüera y Arcas et al. muestra que los programas autorreplicantes emergen espontáneamente de sopas de código aleatorio. Nadie los diseña. Ninguna función de fitness los selecciona. Se arman solos a partir del ruido, toman la sopa y siguen evolucionando. Reproduje el resultado central en unas 300 líneas de código.

#Qué es la Turing completitud

En la década de 1930, tres personas formalizaron de manera independiente qué significa “computación”:

• Alan Turing definió la máquina de Turing: una cinta, un cabezal y un conjunto de reglas para moverse y escribir
• Alonzo Church definió el cálculo lambda: un lenguaje diminuto donde todo es una función
• Kurt Gödel definió las funciones recursivas: una forma de construir funciones computables a partir de unas pocas operaciones básicas

Los tres sistemas resultaron definir exactamente la misma clase de funciones computables. Esta equivalencia es un teorema demostrado. La tesis de Church-Turing va más allá: conjetura que estos formalismos capturan todo lo que es efectivamente computable, no solo que coinciden entre sí.

Un sistema es Turing completo si puede simular una máquina de Turing. Suena a una vara alta; no lo es.

#La vara está absurdamente baja

Para la Turing completitud hacen falta exactamente dos cosas:

• Una forma de ramificar. If/else, cualquier condicional, cualquier mecanismo que elija entre dos caminos según algún estado.
• Una forma de iterar con estado no acotado. Recursión, un contador que puede crecer sin límite, una cinta infinita, cualquier forma de repetición abierta con memoria.

Cualquier sistema que tenga las dos es Turing completo.

El problema es que las dos aparecen de forma natural en casi cualquier sistema diseñado para ser aunque sea un poco flexible. Agregás condicionales porque los usuarios quieren “si pasa esto, hacé aquello”. Agregás repetición porque los usuarios quieren hacer cosas más de una vez. Agregás variables o celdas o registros porque los usuarios quieren guardar resultados intermedios. En algún momento, sin que nadie lo planee, esas features se combinan en una computadora de propósito general.

La Turing completitud sigue apareciendo en sistemas que nunca fueron pensados para cómputo general:

• CSS (animaciones + selectores + calc; discutido, depende del modelo de interacción)
• Excel (fórmulas + referencias circulares o LAMBDA)
• PowerPoint (animaciones con disparadores condicionales)
• Magic: The Gathering (las interacciones entre cartas forman una máquina de Turing)
• El Juego de la Vida de Conway (gliders y compuertas lógicas)
• SQL (CTEs recursivas)
• El preprocesador de C (expansión de macros con trucos de recursión)
• El sistema de tipos de TypeScript (tipos condicionales + recursión)
• La redstone de Minecraft (compuertas lógicas + repetidores)

Nadie se sentó y dijo “hagamos que CSS sea Turing completo”. Agregaron features para dar estilos, y esas features cruzaron el umbral por accidente. La Turing completitud no es una cima alta que escalás, sino un pozo poco profundo en el que caés.

#El problema de la parada como señal

Hay una forma irónica en la que a veces la gente descubre una Turing completitud accidental. Alguien nota que cierta clase de configuraciones puede quedar en un loop para siempre y que no hay una forma general de predecir cuáles van a terminar.

Ese es el problema de la parada (halting problem). Alan Turing demostró en 1936 que ningún algoritmo puede decidir, para todo programa posible, si termina o corre para siempre. No es una limitación práctica sino una imposibilidad matemática.

Una vez que un sistema es Turing completo, el problema de la parada se le aplica. Si descubrís que tu type checker, tu motor de templates o tu sistema de build puede quedar en un loop para siempre de formas que no podés predecir, probablemente construiste un sistema Turing completo por accidente.

#Qué es la autorreplicación

La autorreplicación es un tipo de umbral completamente distinto. Un programa autorreplicante es uno que produce una copia de sí mismo en algún lugar.

John von Neumann estudió esto en la década de 1940 usando autómatas celulares. Quería entender los requisitos mínimos de una máquina que pudiera construir una copia de sí misma. Su autómata autorreplicante era enormemente complejo, con cientos de miles de celdas. Pero el concepto era claro: un sistema que lee su propia descripción y escribe esa descripción en un lugar nuevo.

Los requisitos para la autorreplicación son más mínimos que los de la Turing completitud. No hacen falta condicionales, aritmética ni memoria no acotada. Hace falta:

• Una forma de leer tu propio código
• Una forma de escribirlo en otro lado
• Una forma de repetir hasta que la copia esté completa

Un loop de copia alcanza.

#Los quines no son a lo que nos referimos

Un quine es un programa que imprime su propio código fuente. Es un truco de autodescripción y un acertijo muy querido en la cultura de la programación. Pero los quines no son el tipo de autorreplicación que importa acá.

Un quine corre una vez, se imprime a sí mismo en stdout y termina. No se propaga. No compite. No modifica su entorno.

Los replicadores del paper que vamos a ver hacen algo distinto. Sobrescriben a sus vecinos. Cuando el programa A se ejecuta junto al programa B, A escribe sus propios bytes encima de los bytes de B. Ahora hay dos copias de A. En la siguiente época, las dos copias pueden sobrescribir a dos vecinos más. La diferencia es entre autodescripción y autopropagación: los quines se describen a sí mismos, los replicadores se propagan.

#La autorreplicación es una vara más baja que la Turing completitud

La autorreplicación requiere menos que la Turing completitud.

La Turing completitud requiere condicionales y estado no acotado. La autorreplicación requiere solo un loop de copia. En la variante de Forth estudiada en el paper, un programa de 6 bytes es un autorreplicador completo. En ciertas condiciones, un solo byte (0C) se copia a sí mismo en la cinta del vecino. Un byte.

Si sistemas tan acotados como CSS y Magic: The Gathering cruzan por accidente el umbral de la Turing completitud, entonces la autorreplicación, una hazaña estrictamente más fácil, debería ser todavía más difícil de evitar. Cualquier sustrato en el que los programas puedan leer y escribir su propio código es candidato a la autorreplicación espontánea.

El paper pone esto a prueba.

#Trabajo previo: Tierra y Avida

Los investigadores de vida artificial estudian programas autorreplicantes desde principios de los noventa.

Tierra (1991), de Tom Ray, creó una máquina virtual poblada con programas autorreplicantes. Los programas competían por tiempo de CPU y memoria. Con el tiempo, evolucionaron: aparecieron parásitos que secuestraban la maquinaria de replicación de otros programas, después hiperparásitos que resistían a los parásitos, y después todo un ecosistema de estrategias. Fue un resultado histórico.

Avida (2004), de Charles Ofria, extendió la idea a una plataforma de investigación completa. Los programas podían evolucionar para realizar tareas computacionales a cambio de replicarse más rápido. Avida demostró la evolución de comportamientos complejos a partir de replicadores simples.

Los dos arrancaban con autorreplicadores hechos a mano. Ninguno se preguntó si uno podía armarse de la nada.

#El paper

“Computational Life: How Well-formed, Self-replicating Programs Emerge from Simple Interaction”, de Blaise Agüera y Arcas, Jyrki Alakuijala, James Evans, Ben Laurie, Alexander Mordvintsev, Eyvind Niklasson, Ettore Randazzo y Luca Versari, responde esa pregunta. Sí. Los autorreplicadores emergen espontáneamente del ruido aleatorio.

El paper usa un lenguaje llamado BFF, una extensión de Brainfuck. BFF tiene 10 instrucciones y opera sobre una cinta con dos cabezales: uno para leer y otro para escribir. La propiedad clave es que el programa mismo vive en la cinta. No hay separación entre código y datos. Los programas se automodifican.

#Por qué la automodificación es el ingrediente clave

El diseño experimental no es simplemente “correr programas aleatorios”. Es “concatenar dos programas en una cinta compartida y correrlos juntos”. Esto significa que las instrucciones del programa A pueden escribir encima de los bytes del programa B.

Esto es esencial. Sin eso, los programas se ejecutarían aislados y nada cambiaría. Cada programa haría lo suyo, no produciría ningún efecto duradero sobre ningún otro programa, y la sopa seguiría siendo aleatoria para siempre.

La cinta compartida es el análogo de la química. Las moléculas no solo existen una al lado de la otra. Reaccionan. Rompen y forman enlaces. Cambian la estructura de las otras. De la misma manera, los programas en una cinta compartida cambian el código de los otros. De ahí sale la dinámica.

#Cómo funciona el experimento

El algoritmo de la “sopa primordial”:

1. Crear un pool de 2^17 programas, cada uno de 64 bytes, inicializados con bytes aleatorios
2. En cada época, emparejar programas al azar
3. Para cada par, concatenarlos en una sola cinta de 128 bytes y ejecutarla durante hasta 2^13 pasos
4. Después de la ejecución, dividir la cinta de nuevo en dos mitades de 64 bytes
5. Las mitades modificadas reemplazan a los programas originales
6. Aplicar una pequeña tasa de mutación de fondo (0,024%, inversiones aleatorias de bits)
7. Repetir

No hay presión de selección. No hay señal de recompensa. No hay función de fitness. Los programas simplemente corren, modifican las cintas de los otros y vuelven al pool.

#Cómo se ve la emergencia

Durante las primeras miles de épocas, la sopa parece ruido. La complejidad, medida como entropía de alto orden aproximada mediante compresión con brotli, se mantiene baja. Los programas se modifican entre sí al azar y la distribución de bytes deriva hacia un estado estacionario sesgado por el conjunto de instrucciones de BFF.

Después, de repente, algo cambia. El paper lo llama una “transición de estado”. La complejidad se dispara. La cantidad de programas únicos en la sopa cae bruscamente. Emergió un autorreplicador.

El autorreplicador es un programa que, cuando se concatena con cualquier otro programa, se copia a sí mismo encima de la mitad de la cinta del otro programa. Una vez que aparece uno, se propaga exponencialmente. A las pocas centenas de épocas después de la transición, la mayor parte de la sopa son copias del replicador o variantes cercanas.

El paper rastrea el momento exacto de la emergencia. En un caso de estudio, el primer replicador aparece en la época 2355. Antes de eso hay un loop “pre-replicador” que copia bytes pero que todavía no es un copiador completo. A través de una secuencia específica de interacciones con programas vecinos, el loop adquiere la estructura correcta para convertirse en un autorreplicador completo.

#No es solo la inicialización aleatoria

Una objeción natural: tal vez los autorreplicadores ya estaban presentes en la sopa aleatoria inicial y solo necesitaban tiempo para imponerse.

El paper descarta esto con cuidado. Compara cuatro condiciones experimentales con 1.000 corridas cada una:

• Corridas cortas (128 épocas, inicialización aleatoria): los autorreplicadores aparecen solo 3 veces de 1.000
• Corridas largas (16k épocas, inicialización aleatoria): los autorreplicadores aparecen alrededor del 40% de las veces
• Corridas sin ruido (16k épocas, mutación cero, mezcla fija): los autorreplicadores aparecen alrededor del 50% de las veces
• Corridas con semilla (128 épocas, se inyecta un replicador hecho a mano): los autorreplicadores se imponen alrededor del 22% de las veces

La comparación entre corridas cortas y largas muestra que los autorreplicadores están siendo creados por la dinámica, no simplemente descubiertos en el ruido inicial. La variante sin ruido es particularmente llamativa: incluso con mutación de fondo cero y emparejamiento determinístico, los autorreplicadores siguen emergiendo a una tasa similar. El motor principal es la automodificación a través de la interacción entre programas, no el ruido aleatorio.

#Generaciones de replicadores

El primer replicador que emerge suele ser frágil. En el caso de estudio, el autorreplicador inicial es un palíndromo que se copia a sí mismo al revés. La copia invertida después se vuelve a copiar en la dirección original. Esto funciona, pero tiene una falla: no maneja bien los ceros. Cuando el replicador se encuentra con programas llenos de bytes en cero, inunda la sopa de ceros, una fase de “envenenamiento por ceros” en la que la complejidad se estanca y se degrada.

Después vuelve a pasar algo. Aparece en algún lugar de la sopa un replicador más robusto. Este tiene una estructura |{<,}| que puede sobrescribir ceros. Supera al primer replicador y a sus restos envenenados de ceros, y la complejidad vuelve a subir.

Hay generaciones de replicadores. El primero no es el último. Compiten, y las variantes más robustas reemplazan a las frágiles. Los programas que se copian a sí mismos de forma más confiable se propagan más rápido, una forma de supervivencia diferencial sin una función de fitness explícita.

#La grilla 2D

El paper también corre simulaciones en una grilla 2D de 240 x 135 programas, donde cada programa solo puede interactuar con vecinos a distancia 2 como máximo. Los autorreplicadores siguen emergiendo, pero ahora podés ver cómo se propagan en el espacio. Un replicador aparece en algún lugar de la grilla y se expande hacia afuera como una onda, sobrescribiendo la sopa aleatoria previa a la vida.

La diferencia con la sopa bien mezclada es la velocidad de propagación. En la sopa 0D, un replicador se impone en O(log n) épocas. En una grilla 2D, tarda O(sqrt(n)) épocas porque se propaga por contacto con los vecinos. El escenario 2D también es terreno fértil para que múltiples variantes de replicadores coexistan y compitan, ya que la separación espacial permite que persistan distintos linajes.

#Más allá de BFF

El paper prueba el mismo esquema de sopa primordial con otros sustratos computacionales:

Forth. Un lenguaje basado en pila con un conjunto de instrucciones restringido. Los autorreplicadores emergen todavía más rápido y de forma más consistente que en BFF. Casi todas las 1.000 corridas muestran una transición de estado dentro de las 1.000 épocas (contra un 40% dentro de las 16.000 para BFF). La relativa simplicidad de la autorreplicación en Forth explica esto: un autorreplicador completo puede tener apenas 6 bytes. En ciertas condiciones, un solo byte (0C) que se ejecuta sobre una pila vacía se copia a sí mismo.

Emulación de la CPU Z80. Una grilla 2D de programas de 16 bytes ejecutados en un procesador Z80 real emulado. Acá también emergen autorreplicadores, pero la dinámica es más rica. Primero, una ola de replicadores basados en la pila barre la grilla, aprovechando que las instrucciones PUSH escriben en memoria a través del puntero de pila. Estos forman un ecosistema que coexiste. Después aparece una segunda ola: replicadores que explotan las instrucciones LDIR y LDDR del Z80, que son operaciones dedicadas de copia de bloques. Son más eficientes y superan a las variantes basadas en la pila. Múltiples generaciones de replicadores cada vez más capaces, sobre una arquitectura de CPU real.

Intel 8080. Produce replicadores simples de dos bytes, sin loops, en configuraciones de cinta larga.

SUBLEQ. El contraejemplo. SUBLEQ es uno de los lenguajes Turing completos más simples, con una sola instrucción. A pesar de ser Turing completo, los autorreplicadores nunca emergieron espontáneamente en sopas de SUBLEQ, ni siquiera después de miles de millones de iteraciones. El autorreplicador de SUBLEQ más corto que se conoce tiene 60 bytes (25 bytes en una variante de 4 operandos llamada RSUBLEQ4). Demasiado largo para armarse por accidente a partir de interacciones aleatorias.

#Qué determina la fertilidad

El contraejemplo de SUBLEQ es el resultado más contundente del paper. Muestra que la Turing completitud no es lo que importa: SUBLEQ puede computar cualquier cosa y, sin embargo, no puede producir autorreplicadores espontáneamente, porque el más corto es demasiado largo.

Lo que determina si un sustrato computacional va a generar vida espontáneamente no es su poder teórico. Es la longitud del autorreplicador más corto que admite el lenguaje. Replicadores cortos significan una distancia corta entre el ruido aleatorio y un copiador que funciona. Replicadores largos significan que la sopa queda muerta para siempre.

BFF: replicadores cortos, fértil. Forth: replicadores todavía más cortos, todavía más fértil. Z80: replicadores de longitud media, fértil pero más lento. SUBLEQ: replicadores largos, estéril.

Esta es una propiedad concreta y medible de un sustrato computacional. No tiene que ver con la expresividad, la elegancia o el poder matemático. Tiene que ver con qué tan fácil es construir un copiador por accidente.

#Mi reproducción

Reproduje la sopa BFF 2D en unas 300 líneas de código. El esquema es una grilla de 240 x 135 programas BFF de 64 instrucciones, con un máximo de 2^13 pasos de ejecución por interacción. Cada programa se visualiza como un cuadrado de 8x8 píxeles, coloreado según su contenido.

El intérprete de BFF es el grueso del código. El resto es la lógica de la sopa (emparejamiento aleatorio dentro de un vecindario de radio 2, ejecución, división, mutación) y la visualización.

Lo que ves cuando lo corrés: una grilla de estática de colores. Durante un rato, parece que no pasa nada. Los colores cambian lentamente a medida que los programas se modifican entre sí. Después, en algún lugar de la grilla, aparece una mancha de color uniforme. Crece. En unas pocas centenas de épocas más, toda la grilla está dominada por uno o dos colores, con pequeñas manchas de variación en los bordes donde se encuentran distintos linajes de replicadores.

Eso es un autorreplicador imponiéndose. Nadie lo escribió. Nadie lo seleccionó. Se armó solo a partir de interacciones aleatorias y después le ganó a todo lo demás por el simple hecho de que se copia a sí mismo.

#Preguntas abiertas

La autorreplicación es solo el primer paso. En biología, la replicación fue la chispa, pero la evolución fue el fuego. Una vez que los replicadores compiten por recursos, la presión de selección crea estrategias cada vez más complejas: metabolismo, señalización, cooperación, parasitismo, sistemas inmunes.

¿Puede pasar algo de eso en estas sopas computacionales? Los experimentos con el Z80 lo insinúan: distintas familias de replicadores coexisten y compiten, usando distintas estrategias de instrucciones. Pero todavía no se observó nada remotamente parecido al metabolismo o la cooperación.

¿Qué necesitaría un sustrato para soportar comportamientos más allá de la replicación? El paper no responde esto, pero plantea la pregunta con precisión. Ahora sabemos que la autorreplicación es fácil. La pregunta difícil es: ¿qué viene después?

#Estructura sin diseño

Las otras cosas sobre las que vengo escribiendo van en la dirección opuesta.

En el artículo sobre sistemas de tipos, la idea central es que los humanos diseñan restricciones y el compilador las hace cumplir. Los tipos son estructura que les imponemos a los programas para prevenir errores. En la serie sobre demostración de teoremas, vamos más lejos: los tipos se vuelven proposiciones lógicas, y el compilador verifica verdades matemáticas. Las dos son historias sobre humanos que construyen con cuidado estructura formal y máquinas que la chequean.

Este paper es lo opuesto. Nadie diseñó los autorreplicadores. Nadie escribió un sistema de tipos ni un verificador de pruebas. La estructura emergió del ruido a través de reglas de interacción simples. Los programas de la sopa no tienen tipos, ni propiedades de correctitud, ni garantías formales. Solo se copian, mutan y compiten.

Y sin embargo el resultado tiene una estructura reconocible. Los replicadores tienen lógica interna. Usan loops, condicionales, aritmética de punteros. Las generaciones posteriores son más robustas que las anteriores. En el Z80, las olas sucesivas explotan instrucciones cada vez más poderosas. Algo que parece ingeniería aparece sin un ingeniero.

El artículo sobre sistemas de tipos y la serie sobre demostración de teoremas tratan sobre qué pasa cuando empezás con estructura y la llevás lo más lejos posible. Este paper trata sobre qué pasa cuando empezás sin nada y la estructura aparece igual. Vale la pena entender las dos direcciones. La verificación formal y la emergencia espontánea tratan con programas, tipos y sustratos computacionales. Son el mismo paisaje visto desde extremos opuestos.

#Lecturas recomendadas

• El paper (Agüera y Arcas et al., 2024)
• Repositorio oficial de código (cubff), con implementaciones en CUDA y CPU
• Explorador de autorreplicadores en Z80, de Alexander Mordvintsev
• Tierra de Tom Ray (1991), el predecesor clásico con replicadores iniciales hechos a mano
• Avida (Ofria y Wilke, 2004), plataforma de vida artificial para estudiar la evolución de organismos computacionales
• Autómatas autorreproductores de von Neumann (1966), la base teórica