Jugando con autómatas celulares (16)

2013-09-24

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.

Hasta ahora, hemos trabajado con autómatas de primer orden. Hay autómatas celulares de orden superior en los que el estado futuro no depende únicamente del vecindario actual, sino también de estados anteriores. Para fijar ideas, nos centraremos en autómatas de segundo orden en los que el estado futuro de una celda se basa en el estado de la propia celda en la generación anterior y en el vecindario en la generación actual.

Nuestra biblioteca parece planteada para autómatas de primer orden, pero podemos usarla con autómatas de segundo orden fácilmente; simplemente, nos limitamos a modelar los estados de las celdas con listas de dos elementos: el estado actual y el estado anterior. Esta solución no es la única posible, pero de cualquier manera tenemos que conservar los estados pasados en los autómatas de orden superior. La estructura de datos que estamos usando para representar las celdas (una lista plana) y la forma de trabajar que tiene nuestra biblioteca hace que sea conveniente almacenar los estados pasados de cada celda junto al estado actual. Este esquema permite usar la maquinaria que hemos desarrollado hasta ahora con muy poco código adicional; crearemos alguna función por mera conveniencia.

Vecindarios de orden superior

Por el mismo esfuerzo que nos cuesta crear los vecindarios de segundo orden, creamos los de orden superior arbitrario. Estos vecindarios modificados contienen, para cada celda, una lista cuyo primer elemento es el vecindario original y cuyos demás elementos son los estados anteriores en orden de antigüedad creciente. La función se llamará higher-order-neighbourhoods y aceptará como argumento una función de extracción de vecindarios de primer orden de las que hemos usado hasta ahora. Nuestra higher-order-neighbourhoods ha de devolver una función de extracción de vecindarios modificada que podremos pasar con normalidad a apply-rule. En Scheme, nuestra función es así de cortita:
(define (higher-order-neighbourhoods first-order-neighbourhoods) (lambda (cells) (let ((current-state (map car cells)) (previous-states (map cdr cells))) (map cons (first-order-neighbourhoods current-state) previous-states))))
La traducción más o menos literal a Python 2 es un poquito más engorrosa:
def higher_order_neighbourhoods(first_order_neighbourhoods): def neighbourhoods_and_previous_states(cells): current_state = map(lambda cell: cell[0], cells) previous_state = map(lambda cell: cell[1:], cells) return map(lambda current, previous: tuple(current + list(previous)), first_order_neighbourhoods(current_state), previous_state) return neighbourhoods_and_previous_states
Las «listas» de Python se manejan más bien como vectores y no hay equivalentes a car, cdr y cons, así que la construcción de variables mediante map es un poco prolija y habría quedado un código un poquito más compacto con una técnica mucho más apreciada en Python, lo que se llama en inglés list comprehensions, aunque la ganancia habría sido poco significativa. De igual manera, como las funciones anónimas de Python están apenas a un pasito de ser absolutamente inútiles por limitadas, tenemos que crear una función con nombre interna, neighbourhoods_and_previous. Python no es Scheme y estos ejemplos están más pensados como una ayuda para quien no está del todo familiarizado con Scheme que como prácticas recomendables en Python.

Reglas de segundo orden

Las reglas de los autómatas de segundo orden pueden ser de muchas formas, pero vamos a centrarnos en un caso particular que se aplica a autómatas con dos estados (0 y 1, como los autómatas elementales): partimos de una regla de primer orden y aplicamos a disyunción exclusiva a su resultado y el valor de la celda en la generación anterior:

Si la regla de primer orden dice que el nuevo estado es 0:
- si el estado antiguo es 0, el nuevo estado es 0;
- si el estado antiguo es 1, el nuevo estado es 1.
Si la regla de primer orden dice que el nuevo estado es 1:
- si el estado antiguo es 0, el nuevo estado es 1;
- si el estado antiguo es 1, el nuevo estado es 0.

Esto es lo mismo que la suma módulo 2 del nuevo estado de acuerdo con la regla de primer orden y el estado anterior.

De forma análoga a como hicimos con los vecindarios, vamos a hacer una función modificadora, second-order-rule, que aceptará una regla rule de primer orden y devolverá una regla modificada y preparada para aceptar vecindarios de segundo orden como los que producen los extractores de vecindarios creados con higher-order-neighbourhoods. Naturalmente, tenemos que devolver no simplemente el próximo estado, sino una lista con el próximo estado y el estado actual (que será el estado anterior de la próxima generación). La función, que se llamará second-order-xor-rule, no tiene mucha complicacion en Scheme:
(define (second-order-xor-rule first-order-rule) (lambda (second-order-neighbourhood) (let* ((current-neighbourhood (car second-order-neighbourhood)) (previous-state (cadr second-order-neighbourhood)) (first-order-next-state (first-order-rule current-neighbourhood))) (list (modulo (+ previous-state first-order-next-state) 2) previous-state))))
La versión en Python es así:
def second_order_xor_rule(first_order_rule): def second_order_rule(second_order_neighbourhood): current_neighbourhood = second_order_neighbourhood[0] previous_state = second_order_neighbourhood[1] first_order_next_state = first_order_rule(current_neighbourhood) return ((previous_state + first_order_next_state) % 2, previous_state) return second_order_rule

Pruebas con algunas reglas de autómatas elementales

Probamos varios autómatas elementales hace unas semanas. Hoy vamos a crear resultados con reglas de segundo orden creadas a partir de las de primer orden de entonces. En todos los casos, nuestra primera generación asume un estado anterior idéntico al que tiene. Igual que en aquel artículo, mostraremos gráficamente el resultado con las primeras generaciones en la parte superior y las últimas generaciones en la parte inferior; los píxeles blancos representarán celdas de estado 0 y los píxeles negros representarán celdas de estado 1. La nomenclatura es como la de Wolfram normal, pero con una «R» tras el número de regla para indicar que se trata de una de segundo orden creada mediante la técnica de disyunción exclusiva.

Regla 90R

Podemos generar 160 generaciones a partir de una celda centrada de esta manera:
(step (second-order-xor-rule (wolfram-rule 90)) (append (repeat '(0 0) 159) '((1 1)) (repeat '(0 0) 160)) (higher-order-neighbourhoods cyclic-elementary-neighbourhoods) 160)
Para extraer solamente los estados actuales y dejar fuera los anteriores, podemos usar map:
(map (lambda (generation) (map car generation)) (step …))
El resultado, representado gráficamente, es así:

Evolución de la regla de segundo orden 90R.

Esto recuerda un poco a la aproximación del triángulo de Sierpinski que salía con la regla 90 de primer orden.

Regla 30R

Creamos 160 generaciones así:
(step (second-order-xor-rule (wolfram-rule 30)) (append (repeat '(0 0) 159) '((1 1)) (repeat '(0 0) 160)) (higher-order-neighbourhoods cyclic-elementary-neighbourhoods) 160)
Esto queda representado gráficamente de la siguiente manera:

Evolución de la regla de segundo orden 30R.

Regla 110R

Creamos 320 generaciones así:
(step (second-order-xor-rule (wolfram-rule 110)) (append (repeat '(0 0) 319) '((1 1))) (higher-order-neighbourhoods cyclic-elementary-neighbourhoods) 320)
Esto queda representado gráficamente de la siguiente manera:

Evolución de la regla de segundo orden 110R.

Regla 11R

Partimos de un estado inicial generado pseudoaleatoriamente:
(let* ((generator (uniform-generator 0)) (size 320) (initial-state (unfold (lambda (n) (= n size)) (lambda (n) (inexact->exact (round (generator)))) (lambda (n) (+ n 1)) 0))) (step (second-order-xor-rule (wolfram-rule 11)) (zip initial-state initial-state) (higher-order-neighbourhoods cyclic-elementary-neighbourhoods) size))
El resultado es mucho menos interesante que el de la regla de primer orden:

Evolución de la regla de segundo orden 11R.

Otros artículos de la serie

Categorías: Informática

Permalink: https://sgcg.es/articulos/2013/09/24/jugando-con-automatas-celulares-16/

SGCG