Autómatas Celulares Unidimensionales

Los autómatas celulares unidimensionales están ubicados en matrices donde cada generación esta representada por un renglón de la matriz, siendo el siguiente y el anterior renglón la siguiente y la anterior generación respectivamente. La primera generación está ubicada en el primer renglón.

Cada uno de los autómatas se relacionan con otros ubicados a la derecha o a la izquierda de los mismos.

El precursor de los autómatas celulares unidimensionales es Stephen Wolfram, un bien conocido científico creador del software Mathemática, y ampliamente considerado como el científico más original del mundo, así también como el más importante innovador en la computación científica y técnica de nuestros días.

Según Wolfram, a pesar que la gran cantidad de posibles reglas para autómatas unidimensionales, existen sólo 4 tipos básicos, los cuales son:

- Tipo 1: La evolución deriva en un estado homogéneo, por ejemplo, todos con un mismo valor.

- Tipo 2: La evolución lleva a estructuras estables o periódicas, por ejemplo, líneas verticales.

- Tipo 3: La evolución conduce a un conjunto de patrones bien definidos pero organizados en forma caótica.

- Tipo 4: La evolución lleva a estructuras que son organizadas.

Un tipo muy común de autómata celular unidimensional es el siguiente (ya introducido anteriormente en la definición de autómata celular):

Ejemplo 1: Triángulo de Pascal (el orden de las funciones de transición está diferente que en la muestra anterior)

- Ubicación: Matriz M_(n)=[m(i)]

- k = 2

- E = [m(i-1), m(i+1)]

- d₁: (0, [0,0]) Þ 0 d₅: (0, [1,0]) Þ 1

d₂: (0, [0,1]) Þ 1 d₆: (0, [1,1]) Þ 0

d₃: (1, [0,0]) Þ 0 d₇: (1, [1,0]) Þ 1

d₄: (1, [0,1]) Þ 1 d₈: (1, [1,1]) Þ 0

- Autómata central con estado inicial igual a 1, los demás son 0

El autómata se comporta de la siguiente manera:

Siendo:

- El cuadro superior medio: el estado actual del autómata celular,

- Los cuadros laterales: los estados en que se encuentra el autómata del lado derecho e izquierdo respectivamente.

- El cuadro inferior medio: el nuevo estado actual del autómata.

El gráfico inicialmente generado es:

31 generaciones:

Viéndolo en forma ampliada, después de muchas evoluciones, el gráfico luce así:

299 generaciones:

Podemos observar en el gráfico generado que el patrón inicial se reproduce nuevamente al amplificarse, esto genera un patrón llamado patrón fractal.

El hecho de que una simple regla como la de la función de transición de arriba ya generara un gráfico bastante complejo da la idea de que con simples estados y simples reglas se pueden generar condiciones generales complejas.

Existe una forma de codificar al conjunto Δ: si tomamos a la variable q_h junto con las variables e₁ y e₂ de la entrada E, las representamos como una terna o vector R de 1x3, y a esta terna asociamos el nuevo estado actual q_t, podremos representar a cada función de transición de la siguiente manera:

d_i: (q_h, [e₁,e₂]) Þ q_t es equivalente a d_i:(e₁, q_h, e₂) Þ q_t

Por lo tanto, podremos representar cada función de transición de la siguiente manera:

• d₁: (0, [0,0]) Þ 0 es equivalente a d₁:(0, 0, 0) Þ 0
• d₂: (0, [0,1]) Þ 0 es equivalente a d₂:(0, 0, 1) Þ 1
• d₃: (1, [0,0]) Þ 0 es equivalente a d₃:(0, 1, 0) Þ 0
• d₄: (1, [0,1]) Þ 0 es equivalente a d₄:(0, 1, 1) Þ 1
• d₅: (0, [1,0]) Þ 0 es equivalente a d₅:(1, 0, 0) Þ 1
• d₆: (0, [1,1]) Þ 0 es equivalente a d₆:(1, 0, 1) Þ 0
• d₇: (1, [1,0]) Þ 0 es equivalente a d₇:(1, 1, 0) Þ 1
• d₈: (1, [1,1]) Þ 0 es equivalente a d₈:(1, 1, 1) Þ 0

Hacemos esto pues el vector generado de la combinación de las variables e₁, a y e₂ puede ser expresado por un número binario de 3 dígitos. Esto nos da la posibilidad de asignar a cada valor binario un estado final, para luego poder poner cada estado final en un vector de estados finales ordenados de tal forma que el índice de cada elemento represente el número al cual está asignado dicho estado expresado en decimal. Si el número binario está representado por la variable j, y el estado final por la variable f_i, entonces el vector generado es el siguiente:

R = [f_j]

El vector de nuevos estados del ejemplo de arriba es:

R = [0,1,0,1,1,0,1,0]

Esta es la notación general para una cierta regla unidimensional, la cantidad de elementos para el caso anterior es 2x2x2 o sea 2³, ya que para cada autómata implicado existen 2 posibles estados.

Si el conjunto de estados Q poseyera más de 2 elementos, la forma de representación anterior también es perfectamente aplicable: por ejemplo, si el conjunto Q = [0,1,2], la cantidad de posibles combinaciones de estados entre los vecinos y el autómata será de 3x3x3 o sea 3³. Por lo que concluimos que la fórmula para determinar la cantidad de nuevos estados actuales para una vecindad de 3 autómatas unidimensionales es k³, donde k es el rango de estados como ya lo habíamos explicado.

La notación también funciona si queremos aumentar la cantidad de autómatas implicados, por ejemplo, para una un conjunto Q = [0,1,2] y para un vector E = [a_i-2,a_i-1,a_i+1,a_i+2], la cantidad de posibles estados entre los vecinos y el autómata celular es 3x3x3x3x3 o sea 3⁵ o sea k⁵ o sea k^m+1 donde m es la dimensión de E.

Con esto podemos representar cualquier regla para autómatas celulares unidimensionales. Una forma similar es usada en los autómatas celulares bidimensionales.

Sin embargo, sólo trataremos el caso en el cual la cantidad de vecinos a la izquierda es igual a la cantidad de vecinos a la derecha, la cual expresaremos con la letra r, como lo hace Wolfram. Por lo tanto la variable m puede ser expresada por la fórmula m=2r+1, donde r es el rango de vecindad lateral, que en la regla anterior es de 1.

Si al autómata del ejemplo anterior se le da un estado inicial

donde la función rnd genera números aleatorios entre 0 y 1, o sea, un estado inicial caótico, la gráfica del autómata es la siguiente:

donde podremos observar una auto-organización de los autómatas generando patrones caóticos pero bien definidos, lo que lo convierte en un autómata de tipo 3.

Como ya hemos mencionado, según Wolfram existen 4 tipos autómatas celulares unidimensionales, jerarquizados según su capacidad organizativa. Haga clic aquí para ver ejemplos de ellos.