SGCG

…esto no es un subtítulo…

Ir a: contenido categorías calendario archivo suscripción

Volver arriba

Jugando con autómatas celulares (1)

2013-08-12

Un autómata celular es un objeto matemático que consiste en un conjunto de celdas con valores que van cambiando de un estado a otro con el paso del tiempo, de generación en generación. El estado al que cambia una celda depende del estado en el que se encuentra y del de las celdas que forman su vecindario. Esto parece poco más que un mero divertimento, pero resulta que los autómatas celulares pueden exhibir propiedades sorprendentes con fascinantes comportamientos complejos y organizados que emergen a partir de reglas muy sencillas. Hay autómatas celulares que funcionan como computadores universales (¡aunque quizá poco prácticos!).

En esta serie de artículos vamos a plantear unos sencillos ejercicios prácticos con los que divertirnos con autómatas celulares. Programaremos nuestro propio sistema para jugar con estas cosas. Por hacerlo de alguna manera, haremos el programa en dos lenguajes: Scheme R5RS y Python 2. El primero es un dialecto de Lisp (¿o no?) minimalista y elegante, mientras que el segundo es un lenguaje que ahora mismo es muy popular.

Diseño general

Vamos a desarrollar una pequeña biblioteca para manejar autómatas celulares variados, tanto deterministas como indeterministas y de topología arbitraria.

Partimos de una colección de celdas, cada celda con un estado determinado, en un instante dado. Queremos dar un paso temporal, conocer el estado de las celdas en el siguiente instante. Para ello, tenemos una regla, que no es más que una función que, dado el vecindario de una celda, da el nuevo estado que tendrá dicha celda. Si aplicamos la regla al conjunto de celdas, obtenemos la siguiente generación, las celdas en el siguiente instante. Para hacer esto, tomamos las siguientes decisiones:

Estas ideas quedan plasmada en este código de Scheme tan sencillo:
(define (apply-rule rule cells neighbourhoods) (map rule (neighbourhoods cells)))
Ya está. La función apply-rule es la que itera de un instante temporal al siguiente, la que devuelve la siguiente generación de celdas. Le pasamos la función rule, que es la regla que acepta como argumento el vecindario de una celda y devuelve el próximo estado de la celda. También le pasamos la lista de celdas, cells. Finalmente, el último argumento es la función que extrae los vecindarios, neighbourhoods. Esta función acepta como argumento una lista de celdas y devuelve una lista con los vecindarios de estas celdas. Es así de sencillo.

También podemos hacer lo equivalente en Python:
def apply_rule(rule, cells, neighbourhoods): return map(rule, neighbourhoods(cells))
El funcionamiento es el mismo.

Por ahora, esto no hace nada, ya que necesitamos la regla y el extractor de vecindarios. Tendremos algo en el próximo artículo, en el que crearemos las funciones para un autómata determinista unidimensional cíclico (es decir, con las celdas en una circunferencia).

Otros artículos de la serie


Categorías: Informática

Permalink: http://sgcg.es/articulos/2013/08/12/jugando-con-automatas-celulares-1/