Estructura de la $regla$ $110$

La regla 110 es una autómata celular que evoluciona en una dimensión de orden $(k=2,r=1)$ y presenta algunas características similares a Life, dentro de las estructuras que genera esta regla de evolución puede producir configuraciones fijas, configuraciones periódicas fijas y configuraciones periódicas con desplazamientos, pero a diferencia de Life todas estas estructuras evolucionan sobre un fondo periódico llamado ``ether'' por Cook, además de que puede soportar comportamientos complejos y reproducirse así mismo.

Cook establece una comparación de Life con la regla 110 en [14], es decir, ambas reglas pueden soportar estructuras persistentes que pueden estar fijas o desplazarse a través del espacio de evoluciones, además de que estas estructuras pueden interactuar entre ellas.

La función de transición $\varphi$ para la regla 110 se representa como:

Tabla 5.1:Regla de evolución 110

Regla 110
$\varphi(0,0,0) \rightarrow 0$	$\varphi(1,0,0) \rightarrow 0$
$\varphi(0,0,1) \rightarrow 1$	$\varphi(1,0,1) \rightarrow 1$
$\varphi(0,1,0) \rightarrow 1$	$\varphi(1,1,0) \rightarrow 1$
$\varphi(0,1,1) \rightarrow 1$	$\varphi(1,1,1) \rightarrow 0$

Life y la regla 110 pueden empezar en una configuración inicial aleatoria y despues de un tiempo establecerse en el espacio de evoluciones. Cook muestra tres condiciones importantes que relacionan la regla 110 con la regla de Life.

1. Una célula muerta $x_{i}$ en el tiempo $t$ debe nacer en el tiempo $t+1$, si su vecino derecho $x_{i+1}$ está vivo.

2. Una célula viva $x_{i}$ en el tiempo $t$ debe morir en el tiempo $t+1$, si ambos de sus vecinos $x_{i-1}$ y $x_{i+1}$ están vivos.

3. En otro caso la célula $x_{i}$ en el tiempo $t$ seguirá igual en el tiempo $t+1$.

La regla 110 tiene configuraciones que existen únicamente como configuraciones iniciales, pero estas configuraciones nunca se podrán generar a través de la evolución desde cualquier otra configuración, es decir, no tiene ancestros. Este tipo de configuraciones se les llaman pertenecientes al ``Jardín del Edén'', por ejemplo la configuración 01010 es una configuración que nunca se podrá generar en el diagrama de evoluciones, la única manera de que exista en el diagrama de evoluciones es en la configuración inicial; por su parte Life también tiene configuraciones pertenecientes al ``Jardín del Edén'' [10].

El estudio sobre la regla 110 ha causado un gran interés ya que Cook ha mencionado en [14] que dicha regla puede hacer computación universal, aunque no es claro como se puede llegar a comprobar. Nuestro interés no radica en determinar si dicha regla puede hacer o no puede hacer computación universal, mas bien en establecer las características que relaciona la regla 110 con la regla de Life. Tomando en cuenta que la principal diferencia consiste en que la regla 110 evoluciona en un fondo periódico y Life no, otro punto importante es que si la regla 110 presenta comportamientos similares a Life en una dimensión con sus propias características, entonces implica que dichos comportamientos deben existir en autómatas celulares de dos y tres dimensiones, comportandose como Life pero con un fondo periódico. Por otra parte es importante resaltar que si el sistema de Cook puede simular todo lo que hace Life, se comprobaría que el sistema que planteo von Neumann originalmente en [54], es llevado a un sistema mas sencillo que el modelo de Conway y este modelo es la regla 110.