Propiedades Básicas de las Permutaciones

Analizaremos en detalle el caso en donde $r=1/2$, ya que los demás casos se pueden llevar a éste como hemos visto en la sección 5.2. El proceso indica que debemos hacer permutaciones desde el conjunto $K^{6r}$, para el caso $r=1/2$ el conjunto es $K^3$; para este mismo valor de $r$ tenemos que $\mid L_\phi \mid = Lk^{2r}= Lk$ y que $\mid R_\phi \mid = Rk^{2r} = Rk$.

Primero, comprendamos el funcionamiento del autómata reversible con $r=1/2$, basta una secuencia de $2$ células para que en sus ancestros se fije una única célula central para poder regresar en la evolución. Esta única célula central tiene asociadas $L$ células izquierdas y $R$ células derechas, sin tomar en cuenta esta célula, la parte izquierda de esta construcción es parte de $L_\phi$ y la parte derecha es parte de $R_\phi$.

Figura 5.1: Estructura de un autómata reversible con $r=1/2$

Por supuesto, en las células sucesoras toda combinación es posible, es decir, no puede faltar ninguna vecindad en la regla inversa $\phi ^{-1}$. De esta construcción podemos notar que cada célula sucesora tiene asociadas $L$ células izquierdas ancestras y $R$ células derechas ancestras.

Para cada elemento del conjunto $L_\phi$, la parte sucesora esta relacionada con todas los posibles estados del autómata, lo que hace un total de $k$ extensiones, y como cada una de estas células tiene $R$ células ancestras derechas, cada elemento de $L_\phi$ tiene $Rk$ posibles extensiones derechas, es decir, a todo el conjunto $R_\phi$.

Figura 5.2: Estructura de un autómata reversible con $r=1/2$

Esto nos lleva a las dos primeras propiedades que cumplen estas permutaciones:

Propiedad 1   Sea $(0 \leq i < Lk)$, para cada $x_i \in X$ se tiene asociados a todos los elementos de $Y$.

Como cada elemento de $X$ tiene el mismo número de asociaciones, se mantiene una segunda propiedad.

Propiedad 2   Sean $(0 \leq i < Lk)$ y $(0 \leq j < Rk)$, para cada $x_i \in X$ aparece el mismo número de veces que el resto de los elementos de $X$; tanto en el conjunto de secuencias de la forma $(x_iy_j)$ para $\phi$ como; para el conjunto de secuencias $(y_jx_i)$ para $\phi ^{-1}$. Lo anterior es análogo para cada $y_j \in Y$.

Para las siguientes propiedades, tomemos la siguiente construcción (Figura 5.3) como referencia:

Figura 5.3: Tres células y su evolución

La construcción en la Figura 5.3 representa tres células ancestras, $(a_la_ca_r)$ y al aplicar la regla su evolución $\phi(e_le_r)$. Estas letras subindizadas deben ser entendidas como posiciones específicas de cada célula en la construcción y no deben confundirse con estados del conjunto $K$. Supongamos que en las células $(a_la_c)$ se encuentran en dos elementos fijos del conjunto $K$, entonces, estas células especifican un único estado en $e_l$, en donde el bloque $(a_le_l)$ es un elemento de $L_\phi$; desprendiéndose de esto otra propiedad importante.

Propiedad 3   Sean $(0 \leq i < Lk)$ y $(0 \leq j < Rk)$. Si las células $(a_la_c)$ toman dos valores fijos de $K$, entonces a la secuencia completa $(a_la_ca_r)$ le corresponde un único elemento $x_i \in X$ sin importar que valores tome la célula $a_r$. Del mismo modo, si la misma secuencia $(a_la_ca_r)$ toma dos valores fijos de $K$ en $(a_ca_r)$, le corresponde un único elemento $y_j \in Y$ sin importar que valores toma la célula $a_l$.

En la posición $a_c$ de la Figura 5.3 pueden estar todos los posibles estados de $K$, esto indica que cada estado debe tener $L$ células a la izquierda para formar a un mismo estado y $R$ células a la derecha para el mismo caso, lo que se generaliza para cada estado sin importar en que posición se encuentre en las células ancestras de la construcción utilizada. La observación anterior produce una propiedad mas:

Propiedad 4   Para todo bloque $(a_le_l) \in L_\phi$ deben existir $R$ posibles estados en la posición $a_c$ tal que con el estado en $a_l$ formen el mismo estado en $e_l$. Similarmente para todo bloque $(a_re_r) \in R_\phi$ deben existir $L$ posibles estados en la posición $a_c$ tal que con el estado en $a_r$ formen el mismo estados en $e_r$.

Usemos nuevamente la construcción en la Figura 5.3, sabemos que para generar un estado particular en $e_l$, la célula $a_c$ tiene $L$ posibilidades en $a_l$ y para generar un estado específico en $e_r$, ocurre que $a_c$ tiene $R$ posibilidades. Tomando los $L$ distintos bloques $(a_le_l)$ que solo varían en la posición $a_l$ cuando $a_c$ ese mantiene fijo en un estado, tenemos que en todos estos bloques, las células en $(a_re_r)$ se extienden de la misma forma, si ordenamos de manera descendente las secuencias $(a_la_ca_r)$, variando el estado de $a_r$ desde $0$ a $k-1$, tenemos que los $L$ distintos bloques $(a_le_l)$ compartirán el mismo orden de aparición de las extensiones derechas en $(a_re_r)$.

En este caso, sabemos que $a_c$ tiene $R$ extensiones para generar un estado en particular en $e_r$, dado que el total de extensiones posibles de $a_c$ es $k$, entonces el total de estados que puede tomar $e_r$ es $k/R=L$, entonces, si $a_c$ permanece en un estado fijo, los $L$ bloques en $(a_le_l)$ comparten el mismo orden en las extensiones a la derecha en $(a_re_r)$, donde $e_r$ toma $L$ posibles valores y para cada uno, $a_r$ tiene $R$ posibilidades, entonces, los $L$ elementos de $L_\phi$ comparten las mismas $LR$ extensiones derechas en el mismo orden para $a_c$ fija.

Por la propiedad 4, $R$ estados en $a_c$ son posibles de colocar junto a los $L$ bloques $(a_le_l)$ para formar el mismo elemento en $e_l$, y si para cada estado en $a_c$ existen $LR$ extensiones derechas compartidas, tenemos un total de $RLR$ extensiones derechas a los $L$ bloques $(a_le_l)$ compartiendo el mismo orden, pero como $RLR=Rk$, esto quiere decir que cada uno de los bloques $(a_le_l)$ tiene $Rk$ extensiones derechas compartidas con los demás bloques, en otras palabras, cada uno estos $L$ elementos de $L_\phi$ está conectado con todos los elementos de $R_\phi$, lo que nos lleva ha otra propiedad:

Propiedad 5   Para las células $(a_la_ca_r)$, el conjunto $X$ agrupa $k$ particiones de $L$ elementos cada una. En cada partición los elementos están concatenados en el mismo orden con todos los elementos de $Y$; considerando que las secuencias $(a_la_ca_r)$ se ordenan de manera descendente variando primero los estados de $a_r$ y después los de $a_c$.

Por último, tenemos que para la construcción en la Figura 5.3, cada estado en la célula $e_l$ tiene $L$ estados posibles en la posición $a_l$, a este conjunto de $L$ estados llamémoslo $A_l$; y cada estado en $e_r$ tiene $R$ estados posibles en la posición $a_r$, a este conjunto de $R$ estados denominémoslo $A_r$; dado que el valor de $r=1/2$ es el mismo para $\phi$ como para $\phi ^{-1}$, entonces la secuencia $(e_re_l)$ forma una vecindad de $\phi ^{-1}$, la cual genera un único estado en $a'_c$.

Figura 5.4: Vecindad inversa formada por $(e_re_l)$

En la Figura 5.4; para un estado en $e_r$ existe un conjunto $A_r$ en donde cada elemento de éste puede estar en la célula $a'_c$ y para un estado en $e_l$ existe un conjunto $A_l$ en donde cada elemento es un posible estado de $a'_c$, esto nos induce esta propiedad:

Propiedad 6   Sea $i \in K$ un estado del autómata. Tomemos al conjunto $L_\phi$ dividido en $k$ particiones de $L$ elementos, en donde los elementos de cada partición sólo concuerdan en la posición $e_l$ que puede tomar cualquier valor $i$, los $L$ estados posibles en $a_l$ forman el conjunto $A_{l_i}$. Similarmente dividamos al conjunto $R_\phi$ en $k$ particiones de $R$ elementos, en donde los elementos de cada partición sólo concuerdan en la posición $e_r$ que puede tomar cualquier valor $i$, los $R$ estados posibles en $a_r$ forman el conjunto $A_{r_i}$; entonces:

$$\vert A_{l_i} \cap A_{r_i}\vert =1$$ (5.3)

Hay que hacer notar que esta propiedad no es más que el resultado (Nasu 2) del capítulo 3.