Adrianistán

El blog de Adrián Arroyo


Autómatas celulares unidimensionales en Python

- Adrián Arroyo Calle

Estaba yo leyendo este verano un libro titulado Think Complexity cuando en un capítulo empezó a hablar de los autómatas celulares unidimensionales. El tema me interesó y por eso esta entrada. Veamos primero a qué nos referimos cuando hablamos de esto.

Cuando hablamos a autómatas celulares, nos referimos a pequeñas entidades independientes pero que interaccionan entre sí. Celulares porque son la unidad elemental del universo donde van a existir y autómatas porque deciden por ellas mismas, basadas en un conjunto de reglas predefinido, cuando el tiempo avanza de forma discreta (es decir, a pasos).

Este concepto abstracto puede visualizarse con facilidad si nos imaginamos una rejilla. Cada celda es una célula capaz de cambiar su estado según su entorno.

Los autómatas celulares fueron objeto de estudio de Stephen Wolfram, matemático conocido por haber diseñado el programa Mathemathica y Wolfram Alpha.



Los autómatas celulares unidimensionales son aquellos que forman parte de un universo unidimensional. Es decir, cada célula tiene una vecina a su izquierda y a su derecha. En los bordes se pueden definir varios comportamientos pero el concepto no varía. Pensemos en ello como una tira de celdas.



El estudio de estos autómatas es interesante, ya que pueden generarse patrones/situaciones muy complejas en base a unas reglas sencillas.

¿Cómo se definen las reglas?


Wolfram usó un sistema para definir las reglas de estos autómatas que hoy conocemos como Wolfram Code. Se basa en definir una tabla con los estados presentes de la célula y sus vecinas así como el valor que deberá adoptar en esa situación la célula. Como Wolfram usó células con solo dos estados, todo está en binario, y la parte baja de la tabla es un número de 8 bits. Este número se suele pasar a decimal y así se identifica.

























Estados presentes111110101100011010001000
Estado futuro00110010

Esta tabla representa la Regla 50, porque 00110010 en binario es 50.

¿Cómo se representan?


Una manera muy interesante de representar estos autómatas es poner cada paso en una fila distinta dentro de una imagen.

Una vez que sabemos esto vamos a hacer un programa en Python que nos permita observar la evolución de estos autómatas.

Usaremos el procedimiento original, que es empezar con todos los estados de los autómatas en 0 salvo el del autómata central, que será 1.

La clase Automata


La clase autómata va a contener las reglas, así como un ID y el estado que posee. Además, por cuestiones técnicas conviene guardar el estado anterior que tuvo.


class Automata(object):

rules = list()

def __init__(self,idx=0):
self.idx = idx
self.state = False
self.statePrev = False


Como podéis ver, rules no lleva self, es decir, va a ser una variable compartida entre todas las instancias de Automata. Esto es porque las reglas son idénticas a todos los autómatas.

La clase World


Ahora vamos a definir el universo donde residen estos autómatas. Este universo almacena una lista con los autómatas, se encarga de actualizarlos según las normas y de dibujarlos usando PIL. También he insertado el código que codifica las normas según el número en decimal.


class World(object):
def __init__(self,rule=50):
self.rule = rule
self.im = Image.new("L",(WIDTH,HEIGHT))
self.data = np.zeros(WIDTH*HEIGHT,dtype=np.uint8)
b = bin(rule)[2:].zfill(8)
Automata.rules = [True if c == "1" else False for c in b]
self.list = list()
self.step = 0

def add(self):
automata = Automata(len(self.list))
self.list.append(automata)

def update(self):
for automata in self.list:

automata.statePrev = automata.state
p = self.list[automata.idx - 1].statePrev if automata.idx > 0 else False
n = self.list[automata.idx + 1].state if automata.idx < len(self.list)-1 else False
s = automata.state

if p and s and n:
automata.state = automata.rules[0]
elif p and s and not n:
automata.state = automata.rules[1]
elif p and not s and n:
automata.state = automata.rules[2]
elif p and not s and not n:
automata.state = automata.rules[3]
elif not p and s and n:
automata.state = automata.rules[4]
elif not p and s and not n:
automata.state = automata.rules[5]
elif not p and not s and n:
automata.state = automata.rules[6]
elif not p and not s and not n:
automata.state = automata.rules[7]


def draw_row(self):
if self.step == 0:
middle = len(self.list) // 2
self.list[middle].state = True
for i,automata in enumerate(self.list):
if automata.state:
self.data[self.step*HEIGHT+i] = 255
self.step += 1
def save(self):
self.im.putdata(self.data)
self.im.save("RULE-%d.png" % self.rule)


Con esto ya lo tenemos casi todo. Ahora faltaría poner en marcha todo. La idea es simplemente crear una instancia de World, hacer unas cuantas llamadas a add, y después ir haciendo el ciclo update/draw_row. Una vez hayamos acabado, hacemos save y obtendremos un PNG con la imagen.

Código completo




import numpy as np
from PIL import Image

WIDTH = 5001
HEIGHT = 5001

class Automata(object):

rules = list()

def __init__(self,idx=0):
self.idx = idx
self.state = False
self.statePrev = False

class World(object):
def __init__(self,rule=50):
self.rule = rule
self.im = Image.new("L",(WIDTH,HEIGHT))
self.data = np.zeros(WIDTH*HEIGHT,dtype=np.uint8)
b = bin(rule)[2:].zfill(8)
Automata.rules = [True if c == "1" else False for c in b]
print(Automata.rules)
self.list = list()
self.step = 0

def add(self):
automata = Automata(len(self.list))
self.list.append(automata)

def update(self):
for automata in self.list:

automata.statePrev = automata.state
p = self.list[automata.idx - 1].statePrev if automata.idx > 0 else False
n = self.list[automata.idx + 1].state if automata.idx < len(self.list)-1 else False
s = automata.state

if p and s and n:
automata.state = automata.rules[0]
elif p and s and not n:
automata.state = automata.rules[1]
elif p and not s and n:
automata.state = automata.rules[2]
elif p and not s and not n:
automata.state = automata.rules[3]
elif not p and s and n:
automata.state = automata.rules[4]
elif not p and s and not n:
automata.state = automata.rules[5]
elif not p and not s and n:
automata.state = automata.rules[6]
elif not p and not s and not n:
automata.state = automata.rules[7]


def draw_row(self):
if self.step == 0:
middle = (len(self.list) // 2)
self.list[middle].state = True
for i,automata in enumerate(self.list):
if automata.state:
self.data[self.step*HEIGHT+i] = 255
self.step += 1
def save(self):
self.im.putdata(self.data)
self.im.save("RULE-%d.png" % self.rule)
def __str__(self):
s = str()
for l in self.list:
s += "T" if l.state else "F"
return s

def world_run(rule):
world = World(rule)
for _ in range(WIDTH):
world.add()

for _ in range(HEIGHT):
world.draw_row()
world.update()
world.save()

def main():
rule = input("Rule: ")
try:
rule = int(rule)
if 255 >= rule >= 0:
world_run(rule)
print("Check for the generated RULE-%d.png file" % rule)
else:
raise ValueError
except ValueError:
print("Please, insert a number between 0 and 255")
main()

if __name__ == "__main__":
main()


Algunas reglas importantes


Regla 30


Una de las más importantes a nivel matemático. Ha sido objeto de mucho estudio, sin embargo no vamos a entrar en detalles más allá de su aspecto visual.



Vista ampliada

Regla 110


Esta regla es también muy interesante. ¡Se demostró que era Turing completa!



Vista en detalle

Regla 126


Esta regla no es tan importante, pero personalmente me parece muy bonita.



Vista ampliada

Reglas 57 y 99


Son dos reglas isomorfas. Es decir, son en realidad la misma regla pero aplicada a lados distintos. Elijo estas dos porque se aprecia muy bien el isomorfismo.

Regla 57

Regla 99

Regla 169




Vista en detalle

Regla 129


Regla 90


Es el famoso triángulo de Sierpinski.

Regla 150


Regla 105


Esta regla no tiene isomorfo.

En este artículo no he querido entrar en las complejidades matemáticas de todo esto. Es algo que todavía no entiendo así que no sería sincero por mi parte exponerlo.

Bonus: Richard Feynman y Steve Jobs


Quien me conoce sabe de sobra que uno de los personajes de la historia que más ha influido en mi vida es Richard Feynman. Debo reconocer que entré en un estado de éxtasis al descubrir que Feynman y Wolfram no solo trabajaron juntos, sino que lo hicieron alrededor de la regla 30 antes mostrada. También me sorprendió que Steve Jobs y Wolfram resultasen ser amigos de toda la vida. No dejo de sorprenderme de los contactos de ciertos personajes históricos entre sí.

Feynman a la izquierda, Wolfram a la derecha

Comentarios

j
y si...? esto se aplicara a los píxeles de una imagen? por cierto buen blog, gracias por escribir/compartir.

Añadir comentario

Todos los comentarios están sujetos a moderación