Regla 30» de Wolfram

El matemático Stephen Wolfram se ha decidido a ofrecer dinerito, dinerito a quien resuelva alguno de los tres problemas todavía sin solución relacionados con un autómata celular. Más en concreto se refieren a la llamada Regla 30 (Rule 30), cuyo comportamiento es tan curioso como interesante y de la que –como con otros autómatas celulares– todavía quedan muchos «enigmas por descubrir».

La Regla 30 es un autómata celular binario y unidimensional. La regla define qué sucede con cada celda a cada paso según su estado original y el de las dos celdas vecinas a izquierda y derecha. Como puede haber ocho estados iniciales Wolfram estudió en su momento las 28 = 256 combinaciones posibles con un ordenador. Sólo algunas eran «interesantes».

Regla 30, explicación

En concreto la Regla 30 –llamada así porque esas ocho posibilidades se codifican en el catálogo de las 256 como su resultado, 00011110 (30 en binario)– tiene un comportamiento «aperiódico y caótico». Parece ordenada, pero no mucho. Parece repetir patrones, pero sólo en apariencia: se comporta forma aperiódica. Si se estudia su evolución a cada paso dibujando los estados hacia abajo uno por uno el resultado es un triángulo de formas interesantes pero caóticas.

De hecho es tan caótico que si se toma únicamente la columna vertical central de la que parte el primer estado (un 1) el resultado parece totalmente aleatorio: unos y ceros sin orden ni repetición aparente. Como los dígitos del número pi. De hecho las pruebas de aleatoriedad de todo tipo realizadas lo confirman: no se repite, ni tiene patrones obvios, la frecuencia de 0s y 1s parece tender al 50% y no puede «comprimirse». De hecho hasta se usó durante mucho tiempo como función para generar números aleatorios en el software Mathematica. Pero no está demostrado matemáticamente que todo esto sea así. Y sin eso todo lo que se afirme es pura conjetura. (Como conjeturar que la distribución de los dígitos de pi sea normal.)

La formulación de los tres problemas y sus detalles matemáticos y técnicos están en Rule30Prize.org. En total Wolfram ofrece 30.000 dólares en premios a quien pueda explicar algunas cosas sobre el comportamiento de la Regla 30 y su «columna central», que puede interpretarse como una secuencia binaria de 0s y 1s:

  1. ¿Es una secuencia no-periódica?
  2. ¿Es la frecuencia de ambos valores la misma como promedio? (50%)
  3. ¿Es necesaria una potencia de cálculo de O(n) para calcular la n-ésima celda?

El artículo en el que Wolfram anuncia y explica el desafío de la Regla 30 es sumamente interesante incluso para quienes no vayan a participar. Incluye, como ya hizo en su libro A New Kind of Science toda la historia del descubrimiento de la Regla 30 y lo que se ha ido descubriendo sobre ella. También sobre las generalizaciones e investigaciones hasta la fecha, así como otras disquisiciones más complejas sobre computación y su significado matemático e incluso físico. Para quien esté interesado en los autómatas celulares es lectura obligada.

Los problemas acerca de la Regla 30 son de una importante magnitud, pero además de eso es que llevan tantos años abiertos que quien los resuelva seguramente consiga algo más que los 30.000 dólares (o una parte de ellos). Hace tiempo Wolfram planteó un reto parecido y poco después hubo premio. A quien los resuelva le espera la fama mundial y probablemente un jugoso contrato para trabajar con el propio Wolfram, que sin duda quedaría impresionado por la hazaña.

(Vía Pickover.)

Relacionado:

# Enlace Permanente