La Regla 110 de Wolfram

La Regla 110 de Wolfram es un notable autómata celular unidimensional de la clasificación de reglas «elementales» de Stephen Wolfram. Cada celda en esta cuadrícula lineal puede estar en uno de dos estados: 0 (apagado) o 1 (encendido). Con cada paso, la siguiente fila de celdas se determina mirando los tripletes de la fila actual — cada celda más sus dos vecinos. El patrón de qué tripletes producen un 1 en la siguiente generación está codificado por el número binario 110.

A pesar de su definición mínima — solo unos pocos bits describiendo qué arreglos locales se vuelven «encendidos» — la Regla 110 demuestra un comportamiento increíblemente rico y complejo. Se ha demostrado que es Turing completa bajo ciertas condiciones iniciales, colocándola a la par con sistemas que pueden, en teoría, realizar computación universal.

Cómo funciona →

La Regla

En la terminología de autómatas celulares elementales, el número de regla decimal 110 corresponde al patrón de bits 01101110 cuando se lee desde el triplete «111» hasta el «000». Esto significa que ciertos tripletes (como 110, 101, 011, 001) producen una celda viva en la siguiente generación, mientras que otros resultan en una celda muerta.

A pesar de la simple convención de nombres, los comportamientos que emergen pueden ser sorprendentemente complejos. Verás regiones caóticas, patrones repetitivos y todo tipo de interacciones impulsadas por estas simples reglas de tripletes.

Emergencia y Complejidad

Uno de los aspectos más intrigantes de la Regla 110 es cómo una sola fila de bits puede evolucionar hacia estructuras que parecen partículas en movimiento, colisiones o frentes de onda. Pequeños cambios en la fila inicial pueden alterar drásticamente el tapiz que se despliega, destacando la sensibilidad del sistema a las condiciones iniciales. Esta complejidad emergente surge puramente de interacciones locales — no se requiere coordinación central.

En ciertas configuraciones, presenciarás regiones estables, «Gliders» y expansiones repetitivas o caóticas que subrayan la profundidad del sistema. Los investigadores han estudiado este autómata extensamente para entender cómo sistemas deterministas simples pueden exhibir patrones que parecen aleatorios o son al menos computacionalmente irreducibles.

Completitud de Turing

La Regla 110 puede configurarse para computar cualquier cosa que una máquina de Turing universal pueda, haciéndola Turing completa. Esto significa que si configuras la fila inicial de la manera correcta, puedes teóricamente emular operaciones lógicas, memoria y cualquier elemento computacional fundamental dentro de este pequeño autómata. Es una demostración impresionante de que la complejidad puede surgir incluso del conjunto de reglas más simple — son las interacciones locales repetidas a lo largo del tiempo las que producen un comportamiento poderoso.

Descripción General del Algoritmo

A continuación se muestra un enfoque sencillo para calcular cada nueva fila. Opcionalmente envolvemos los bordes para que las celdas de un lado puedan ver vecinos del lado opuesto. Si esto está deshabilitado, los bordes más allá de la cuadrícula se consideran «muertos»:

// Rule 110 transition table - maps each 3-bit pattern to its next state
const transitions = {
  // pattern => next state
  '111': 0,
  '110': 1,
  '101': 1,
  '100': 0,
  '011': 1,
  '010': 1,
  '001': 1,
  '000': 0
};

Y así es como lo aplicamos durante cada actualización (aunque nuestra implementación final usa el enfoque de desplazamiento de bits, esta tabla es una expresión alternativa de qué tripletes producen una celda viva):

function computeNextRow(currentRow, wrapEdges) {
  const length = currentRow.length;
  const newRow = new Array(length).fill(0);

  for (let i = 0; i < length; i++) {
    const leftIndex  = wrapEdges ? (i - 1 + length) % length : i - 1;
    const rightIndex = wrapEdges ? (i + 1) % length : i + 1;

    const left   = (leftIndex < 0 || leftIndex >= length) ? 0 : currentRow[leftIndex];
    const center = currentRow[i];
    const right  = (rightIndex < 0 || rightIndex >= length) ? 0 : currentRow[rightIndex];

    const pattern = (left << 2) | (center << 1) | right;
    newRow[i] = (110 >> pattern) & 1;
  }
  return newRow;
}