Otra nueva especulación (errónea), sobre la regla 30 de Wolfram

Ya hablé aquí de una serie de especulaciones sobre la regla 30 de los autómatas celulares unidimensionales. Stephen Wolfram, quien los ha estudiado a detalle, ha encontrado que la regla 30 de estos autómatas genera un patrón que parece ser aleatorio, cosa que no pasa con muchas de las otras reglas. De hecho, como mencioné en el artículo al que hago referencia, Wolfram hace tres preguntas, al público en general, esperando que ahí afuera haya alguien que ataque estos problemas. Para motivarlos ha ofrecido unos 10 mil dólares por pregunta solucionada. Estas son las tres cuestiones que Wolfram quiere responder:

¿Puede la columna central mantenerse siempre no periódica?

¿El color de cada célula en el centro -en promedio- ocurre con igual frecuencia en la columna central?

¿El cálculo de la enésima célula en el centro requiere de al menos un esfuerzo computacional de O(n)?

Para tratar de resolver la primera pregunta, lo que hice fue primero usar la idea de Ulam, que nació de una ociosidad. Estaba Ulam en una conferencia y se encontraba aburrido. Entonces decidió dibujar los números primos en una hoja pero en una espiral. Para su sorpresa, halló que había ciertos patrones. Un clásico ejemplo de serendipia, que es un descubrimiento o un hallazgo afortunado, valioso e inesperado que se produce de manera accidental, casual, o cuando se está buscando una cosa distinta.

Lo que encontré usando la espiral de Ulam es que el comportamiento de los ceros y unos, de la columna central del autómata celular de a regla 30, no mostraba patrón alguno. Cuando estaba programando el problema, pensé que quizás podría dar luz al asunto, pero hallé que no hay patrón alguno usando esta técnica.

Pero hace unas semanas se me ocurrió otra idea, creada por Christopher Langton, que creó hace unos 40 años un programa en una Apple II, el cual era una "hormiga" (un punto en la pantalla), que se movía de acuerdo a ciertas reglas. Todo lo que hizo puede verse aquí. 

Pues bien, con esta idea, se me ocurrió que podía tomar el archivo de un millón de ceros y unos, de la columna central de la regla 30, y procesarlos gráficamente de acuerdo a la siguiente idea: 

Si encuentro un 0, me muevo derecho, sin girar. Si el nuevo valor es igual al anterior, sigo en esa dirección. Si de 0 cambio a 1, entonces lo que hago es un giro a la derecha. Si el siguiente valor sigue siendo un 1, sigo en la dirección que acabo de tomar. Si cambia a 0, entonces vuelvo a girar a la derecha y así sucesivamente. ¿Qué tipo de imagen se generará con esta idea?

Este es el video del software corriendo:

Especulando con la regla 30 de Wolfram

Al inicio me pareció que se generaba un bloque y después se hacía un camino y se creaba otro bloque. ¿Podría haber un patrón ahí? Dejé el software corriendo y eventualmente hallé que no parece haber manera de tener un patrón claro, ni siquiera puede decirse que haya un patrón borroso, valga la expresión. Dicho de otra manera, otra idea que choca con pared.

Cabe decir que en un millón de iteraciones de la regla 30, encontré que la cantidad de '0' (ceros) es de 500,768 y la de '1' (unos) es de 499,231 (*).

Algo curioso es que en la generación de la imagen encontré que se generaba un "rostro" (ver siguiente imagen). ¿Podría ser la imagen de Jesús? Nah, es una simple pareidolia, lo cual se define como un fenómeno psicológico donde un estímulo vago y aleatorio (habitualmente una imagen) es percibido erróneamente como una forma reconocible.

Así las cosas, seguiremos investigando.

____

(*) Estrictamente la cuenta da 999,999. La razón de esto es que puse el límite en ese valor en mi programa por error. Sin embargo, no cambia nada este detalle.

La regla 30 de los autómatas de Wolfram

Stephen Wolfram es un científico de primer nivel y además un exitoso hombre de negocios. Es el creador de Mathematica, uno de los programas más poderosos para hacer matemáticas simbólicas, el cual además tiene incorporado un lenguaje de programación muy útil para un sinfín de quehaceres matemáticos. Además de eso, Stephen Wolfram ha dedicado parte de su vida al estudio de los autómatas celulares unidimensionales e incluso hay una colección completa de los artículos que se han publicado al respecto, junto con otros autores.

Los autómatas celulares son un modelo matemático y computacional para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros. Se basa en definir reglas ciegas a las "células" (pixeles en la pantalla), de manera que evolucionen estas a tiempos discretos para ir viendo lo que ocurre a través del tiempo. Por ejemplo, en dos dimensiones tenemos el famoso "juego de la vida" de Conway, que ha sido muy estudiado por matemáticos, físicos y biólogos, pues tiene comportamientos de auto-organización asombrosos en muchos casos. 

Wolfram ha estudiado los autómatas celulares en una sola dimensión, es decir, todas las células se encuentran en una línea y se reproducen en el tiempo (o mueren), de acuerdo a ciertas reglas. Por ejemplo, la regla 30 es 00011110, y se ejemplifica así: si hay tres células en la línea (y tomamos la célula de en medio), esta muere por sobrepoblación. Si no hay célula, nada surge en la siguiente generación. Dos células a la izquierda no se reproducen pero dos células a la derecha sí lo hacen. Una célula sola se reproduce en la siguiente generación siempre, ya sea estando a la izquierda, centro o derecha, etcétera

Lo que da la siguiente gráfica, poniendo una sola célula en la primera generación:

Wolfram, sin embargo, tiene aún problemas por resolver con respecto a esta regla 30, la cual parece generar una imagen caótica. De hecho, ha anunciado un premio de 30 mil dólares (10 mil por pregunta resuelta), a quien responda lo siguiente:

1. ¿Puede la columna central mantenerse siempre no periódica?
2. ¿El color de cada célula en el centro -en promedio- ocurre con igual frecuencia en la columna central?
3. ¿El cálculo de la enésima célula en el centro requiere de al menos un esfuerzo computacional de O(n)?

Stephen Wolfram dice al respecto de estas preguntas: "No sé si estos problemas son de dificultad comparables o si alguno de ellos puede resolverse mientras que los otros pudiesen mantenerse sin solución por mucho tiempo. Estoy seguro, sin embargo, que el resolver cualquiera de estos problemas será un logro significativo".

Pensando en este problema, y porque los autómatas celulares son mis viejos amigos (trabajé con ellos desde mi tesis de licenciatura), decidí pensar un poco más sobre ellos. Se me ocurrió trabajar sobre las primera pregunta. He leído un poco de lo que otros han hecho y de pronto se me ocurrió que quizás la no-periodicidad podría ser parecida a la que se presenta en los números primos y además, recordé la espiral de Ulam, la cual descubrió en una aburrida conferencia el matemátiuco Stanislaw Ulam. Tal vez a nadie se le había ocurrido la feliz idea de colocar la columna central dee los autómatas celulares unidimensionales, en la regla 30, de esta manera. Entonces me apliqué y escribí un sencillo programa que hace la tarea de colocar esa columna central de células en forma de espiral cuadrada.

Por suerte, no tuve que hacer el cálculo de la columna central de la regla 30, pues ya alguien lo hizo aquí, que contiene un millón de valores. Más que suficiente para probar. Ejecuté entonces mi programa. Generé una imagen de 1000 x 1000 pixeles (con Photoshop), y la puse en un componente imagen en mi software en Delphi y me dispuse a ver si había algún patrón como en el caso de los números primos en la espiral de Ulam. Pero ¡ay! no hallé ningún patrón gráfico...

Quizás mi ingenuidad no conoce límites y es probable que antes alguien se le haya ocurrido esta idea, pero Wolfram no la menciona. Pensé que sería maravilloso si se daba algún patrón. Bueno, es un primer intento. A seguir discurriendo sobre el problema.