Los autómatas celulares son sistemas muy fáciles de calcular: se tiene un conjunto trivial de reglas que se aplican en cada paso y se observa simplemente cómo la configuración inicial evoluciona.
Uno de los autómatas celulares más conocidos es el del juego de la vida, de John Conway, del que han escrito ríos de tinta.
Sin embargo, a diferencia del juego de la vida de Conway, que se ejecuta en una malla de dos dimensiones, Stephen Wolfram ha estudiado los autómatas en una sola dimensión.
De hecho tiene un enorme libro en donde trata el tema a profundidad. El libro puede leerse en inglés aquí.
Las reglas de Wolfram
Wolfram, un connotado científico estadounidense ha estudiado y clasificado las reglas simples en una sola dimensión. Así como ocurre con el juego de la vida de Conway, se empieza no con una serie de células en dos dimensiones, sino que se ponen las células en una sola línea.
De acuerdo a la regla que genera el comportamiento del autómata , se aplica ésta y se despliegan los resultados abajo de la línea original de células.
Se genera así, de manera sorprendente, patrones muy interesantes. Algunos son simétricos y otros no. Lo curioso es que la regla 30 es diferente a las demás.
El siguiente patrón describe la regla 30, que es particularmente interesante:
111 –> 0
110 –> 0
101 –> 0
100 –> 1
011 –> 1
010 –> 1
001 –> 1
000 –> 0
Donde «1» representa una célula y «0» representa un lugar vacío. Así, la regla 30 (como todas las demás) se genera usando tres casilleros en donde están todas las combinaciones de células.
Según la configuración que se defina, se puede numerar la regla fácilmente, usando los valores resultantes de la regla para cada combinación. Una vez que se tiene esto, lo siguiente es clasificar el comportamiento de las posibles reglas.
La regla 30 es la más interesante de las 256 posibles reglas. Aparentemente puede producir un patrón pseudo aleatorio. El interés es que se genera un comportamiento complejo a partir de una regla muy simple y esto no parece ser lo esperado. Lo más curioso quizás es que hasta donde se sabe, hay que hacer la simulación explícita para generar el autómata.
En la regla 30 se observa un comportamiento regular a la izquierda, pero en la parte derecha del patrón aparece un patrón complejo y continúa evolucionando sin repetirse, en la medida que se incrementa el número de generaciones calculadas.
¡Premio en efectivo!
Por supuesto que hay muchas cosas que no sabemos sobre los autómatas celulares y Wolfram ha decidido pedir ayuda.
Ha elegido tres «teoremas» sobre el particular de la regla 30 y ofrece 10 mil dólares por cada uno de ellos resuelto.
Problema 1: ¿La columna central siempre aparece como no-periódica? En otras palabras, se puede demostrar que la columna central nunca se repite o probar que es eventualmente periódica. Por lo pronto se sabe, a partir de simulaciones por computadora, que no hay periodicidad después de mil millones de pasos.
Problema 2: ¿El color de las células (blanco y negro) ocurren en promedio con la misma frecuencia en la columna central? Si se calcula la razón de espacios (blanco) contra las células (negro), parece que converge a uno en la medida que el número de generaciones se incrementa. Pero ¿qué es exactamente ese 1?
Problema 3: ¿El cálculo de la enésima célula de la columna central requiere al menos un esfuerzo O(n)? Si se calcula directamente la enésima célula para la regla, encontramos que la complejidad es O(n2). ¿Hay un atajo para esto?
Aunque la problemática no parece complicada, nadie sabe a ciencia cierta cómo atacar estos problemas. Tampoco parece que se entiende muy bien qué tan complejos son estos problemas.
Tal vez se requiera de nuevas técnicas, nuevos algoritmos, nuevas matemáticas, para tratar de dar una solución a estos problemas. Por otra parte, ¿qué tal que la solución es una obviedad y no la estamos viendo?
Wolfram piensa que estos problemas merecen esta cantidad de dinero para quienes los resuelvan.
Y si da ese dinero es porque tiene un interés particular, pues su libro de autómatas habla de lo que él ha propuesto como la base de toda una nueva física. Sin embargo, si no se pueden resolver estos problemas simples, no parece que podamos seguir adelante en la teoría de Wolfram al respecto.
Los detalles del concurso pueden verse aquí. Wolfram además ha escrito un mensaje en su blog donde indica lo que piensa al respecto de estos problemas. Sin duda el razonamiento de Wolfram es importante para todo aquel que se embarque en estos problemas de la regla 30.
Para quien quiera jugar con los autómatas celulares en una dimensión, La_Morsa ha cedido su software para que lo descargue gratuitamente quien tenga interés. Este es el enlace.
