Autómata celular elemental

No obstante, hay un autómata celular elemental (regla 110, definido abajo) capaz de computación universal.

Existen 8 = 23 configuraciones posibles para una célula y sus dos vecinos inmediatos.

Cada configuración actual posible está escrita en orden, 111, 110, ..., 001, 000, y el estado resultante para cada una de estas configuraciones está escrito en el mismo orden e interpretado como la representación binaria de un número entero.

Estas reglas exhibirán el mismo comportamiento hasta la reflexión a través de un eje vertical, y por lo tanto son equivalentes en un sentido computacional.

De los 256 autómatas celulares elementales, hay 88 que son desiguales bajo estas transformaciones.

Esta es la secuencia de números Jacobsthal y tiene la función generadora: tiene la expresión de forma cerrada Tener en cuenta que la regla 156 genera la misma secuencia.

Esto puede ser obtenido por tomar filas sucesivas del triángulo de Pascal módulo 2 e interpretándolas como enteros en base 4.

Las 88 reglas inequitativas son las siguientes, evolucionadas a partir de condiciones iniciales aleatorias: En algunos casos el comportamiento de un autómata celular no es inmediatamente obvio.

Por ejemplo, para la Regla 62, las estructuras que interactúan se desarrollan como en un Clase 4.

La regla 73 es clase 2 ya que en cualquier momento hay dos unos (1) consecutivos rodeados por ceros (0), esta característica se conserva en generaciones sucesivas.

Estas paredes se formarán con probabilidad 1 para las condiciones iniciales completamente aleatorias.

La regla 54 es la clase 4, pero sigue siendo desconocida si es capaz de computación universal.