SGCG

Volver arriba

Jugando con autómatas celulares (9)

2013-08-31

Hace varios artículos, planteamos un interesante proyecto: una pequeña biblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.

Seguimos construyendo funciones para hacer una biblioteca de autómatas celulares razonablemente general y práctica. Hoy vamos a crear funciones para trabajar con autómatas elementales. Ya estamos a punto de generalizar aquel trabajito que hicimos sobre la regla 90. Un autómata celular elemental es unidimensional (extendido de izquierda a derecha, por ejemplo), sus celdas solamente tienen dos estados (0 y 1, digamos) y sus vecindarios consisten en la celda inmdiatamente a la izquierda, la propia celda y la celda inmediatamente a la derecha. Las normas quedan escritas de forma muy compacta mediante lo que se conoce como la notación de Wolfram. Parece que lo único que tenemos que preparar es la extracción de los vecindarios (algo fácil gracias a la función cyclic-cartesian- que creamos en el anterior artículo) y la generación de normas (también fácil gracias a la función deterministic-rule que creamos hace unos pocos artículos). Antes de hacer eso, con el fin de facilitarnos nun poco la vida, prepararemos unas pocas funciones auxiliares más.

Función de repetición

En Python 2, podemos construir cómodamente una lista de tamaño n cuyos elementos son todos un cierto objeto o de la siguiente manera:
n * [o]
Scheme R5RS no tiene el equivalente a esto, pero nos convendrá disponer de ello. Podemos improvisarlo de varias maneras; aquí haremos uso de nuestra función unfold para crear una función repeat que acepta un objeto object y el número times de veces que aparecerá repetido en una lista:
(define (repeat object times) (unfold (lambda (n) (< n 1)) (lambda (n) object) (lambda (n) (- n 1)) times))

Paso de entero a lista de bits

Resulta que la operación de extracción de bits es similar a la operación de paso de índices planos a índices multidimensionales en un espacio en el que todas las dimensiones tienen tamaño 2 y el número de dimensiones es igual al número de bits. En general, la extracción de dígitos es igual que el paso de índices planos a índices multidimensionales en un espacio en el que todas las dimensiones tienen como tamaño la base y el número de dimensiones es igual al número de dígitos a extraer. Podemos definir una función de extracción de dígitos general integer->digits que acepta un número number, una base base y el número de dígitos a extraer number-of-digits; y devuelve la lista de dígitos:
(define (integer->digits number base number-of-digits) (flat->multidimensional (repeat base number-of-digits) number))
La extracción de bits es un caso particular:
(define (integer->bits number number-of-bits) (integer->digits number 2 number-of-bits))
El número de dígitos a extraer es algo importante porque los ceros a la izquierda sí son significativos en la especificación de las normas de nuestros autómatas elementales.

El código anterior de Scheme tiene una traducción inmediata a Python:
def integer_to_digits(number, base, number_of_digits): return flat_to_multidimensional(number_of_digits * [base], number)
def integer_to_bits(number, number_of_bits): return integer_to_digits(number, 2, number_of_bits)

Paso de lista de bits a entero

La operación inversa a la anterior puede ser útil. Es análoga al paso de índices multidimensionales a índices planos. Definimos la función digits->integer que funciona a la inversa de integer->digits, pero no necesita que le pasemos el número de dígitos:
(define (digits->integer digits base) (multidimensional->flat (repeat base (length digits)) digits))
Como antes, el paso de bits a entero bits->integer es una particularización:
(define (bits->integer bits) (digits->integer bits 2))

La versión en Python de todo esto es similar:
def digits_to_integer(digits, base): return multidimensional_to_flat(len(digits) * [base], digits)
def bits_to_integer(bits): return digits_to_integer(bits, 2)

Extracción de vecindarios

Vamos a construir la función extractora de vecindarios. Nuestros vecindarios contendrán la celda situada a la izquierda, la celda actual y la celda situada a la derecha. Esto es muy fácil de conseguir gracias a la función cyclic-cartesian-neighbourhoods que creamos en el anterior artículo:
(define (cyclic-elementary-neighbourhoods cells) (cyclic-cartesian-neighbourhoods cells (list (length cells)) '((-1) (0) (1))))
Es igual en Python:
def cyclic_elementary_neighbourhoods(cells): return cyclic_cartesian_neighbourhoods(cells, [len(cells)], [[-1], [0], [1]])
Los parámetros de la función cyclic-cartesian-neighbourhoods son un poco engorrosos de pasar cuando trabajamos con autómatas unidimensionales: la dimensión va en una lista y cada posición relativa de los vecinos también va en una lista. Es así como hicimos la función y hay que quererla igual, pero este aspecto es mejorable con poco esfuerzo.

La función cyclic-elementary-neighbourhoods acepta como argumento una lista de celdas cells y devuelve los vecindarios de autómatas elementales correspondientes con la restricción de que se supone que el autómata se repite periódicamente y la lista de celdas contiene un periodo.

Generación de normas

El código de Wolfram establece una forma muy compacta para describir reglas de autómatas celulares elementales. Cada norma está caracterizada por un número entero entre 0 y 255. Si asociamos cada uno de los 8 posibles estados de los vecindarios elementales de una celda (dispuestos en un determinado orden que veremos más adelante) con los bits de la expansión binaria de 8 bits del número de norma, nos sale una tabla de correspondencias entre el estado del vecindario y el próximo estado de la celda, es decir, la descripción de una norma determinista. Podemos crear las normas de esta manera:

1. Convertimos el número de norma en su expansión binaria de 8 bits. Esto podemos hacerlo con integer->bits.
2. Creamos una lista de 8 los posibles estados de los vecindarios elementales:
   ((1 1 1) (1 1 0) (1 0 1) (1 0 0) (0 1 1) (0 1 0) (0 0 1) (0 0 0)).
   Son las expansiones binarias de 3 dígitos de los números del 7 al 0, con lo que podemos generarlas aplicando integer->bits sobre un rango generado con range.
   Creamos una tabla en la que cada uno de los posibles 8 estados de los vecinos está asociada con el bit correspondiente de la expansión binaria del número de norma. Esto podemos hacerlo con zip (o con zip sobre dict en Python).
   Creamos la función norma mediante deterministic-rule.

Todo esto queda plasmado en el siguiente código de Scheme:
(define (wolfram-rule rule-number) (define patterns (map (lambda (integer) (integer->bits integer 3)) (reverse (range 0 8 1)))) (define states (integer->bits rule-number 8)) (define table (zip patterns states)) (deterministic-rule table))
La versión en Python es igual.
def wolfram_rule(rule_number): patterns = map(lambda integer: tuple(integer_to_bits(integer, 3)), range(0, 8, 1)[::-1]) states = integer_to_bits(rule_number, 8) table = dict(zip(patterns, states)) return deterministic_rule(table)
Esta función acepta un número de regla rule-number y devuelve la regla correspondiente según el código de Wolfram.

Otros artículos de la serie

• Introducción.
• Pequeño autómata de demostración.
• Función para crear reglas deterministas.
• Funciones para sacar por pantalla las listas de celdas.
• Funciones auxiliares útiles.
• Más funciones auxiliares útiles.
• Funciones para trabajar con mallas cartesianas.
• Extracción de vecinos en mallas cartesianas cíclicas.
• Funciones para crear generaciones sucesivas cómodamente.
• Prueba con varios autómatas elementales.
• Funciones para imprimir autómatas bidimensionales cartesianos.
• Juego de la vida de Conway.
• Funciones para trabajar con autómatas no deterministas.
• Autómata no determinista: modelo del incendio forestal.
• Autómatas de segundo orden.
• Mejora del rendimiento mediante memoización.
• Más pequeñas modificaciones para acelerar notablemente el código.
• Salida de imágenes.

---

Categorías: Informática

Artículos publicados el mismo mes

Permalink: http://sgcg.es/articulos/2013/08/31/jugando-con-automatas-celulares-9/

Volver arriba