Autómatas celulares unidimensionales en Python
28/08/2017
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.
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.
Esta tabla representa la Regla 50, porque 00110010 en binario es 50.
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 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.
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.
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.
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.
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
Esta regla es también muy interesante. ¡Se demostró que era Turing completa!
Vista en detalle
Esta regla no es tan importante, pero personalmente me parece muy bonita.
Vista ampliada
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
Vista en detalle
Es el famoso triángulo de Sierpinski.
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.
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
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 presentes | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| Estado futuro | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
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 ampliadaRegla 110
Esta regla es también muy interesante. ¡Se demostró que era Turing completa!
Vista en detalleRegla 126
Esta regla no es tan importante, pero personalmente me parece muy bonita.
Vista ampliadaReglas 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 99Regla 169
Vista en detalleRegla 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