Modelo de Alvi Ray Smith III(1968)

   , , ,   

Este modelo fue presentado en 1968 y posteriormente revisado en 1971. Muchos de los trabajos anteriores al de Ray Smith III, se hicieron con base en el modelo original de John von Neumann. También se dieron a conocer algunos estudios del modelo de von Neumann por parte de J. W. Thatcher en 1964, y un poco más tarde se mencionarían fundamentos de autómatas celulares, manteniendo la idea original de von Neumann por M. A. Arbib y en 1968 por E. F. Codd.


Sin embargo en 1971 Alvi Ray Smith III dio a conocer su modelo que está basado en la idea de usar funciones parciales recursivas, y no en simular una cinta y la cabeza lectora de la cinta, como en el modelo de von Neumann.

El trabajo de Ray Smith III inicia con el teorema de la ``Máquina universal de Turing'' en términos de funciones parciales recursivas, y entonces hace analogías entre los números naturales y las configuraciones globales de un autómata celular, mencionando la idea de computación en espacios celulares. Dado un espacio celular $ Z$ , una función de transición global $ F$ , una configuración global inicial $ c$ y una función parcial recursiva $ g:\mathbb{N}\rightarrow\mathbb{N}$ , se dice que $ c$ calcula $ g$ si:

  1. Existe una secuencia de configuraciones globales $ (d_n)$ , cada una diferente de la configuración global inicial $ c$ , que es una enumeración efectiva de las configuraciones globales (no necesariamente de todas).
  2. Existe una función parcial recursiva $ h:(\chi_i)\rightarrow(\chi_i)$ tal que, si $ g(n)$ está definida, entonces hay un momento $ t_0$ tal que
    $\displaystyle h(F^{t_0}(c\cup d_n))=d_{g(n)}$
    Donde $ (\chi_i)$ es una secuencia de configuraciones globales que representan evoluciones del autómata. Se puede ver esta función $ h$ como una función decodificadora, y a la configuración global $ d_{g(n)}$ como el resultado del cálculo.
  3. Hay un número $ m\geq 1$ y una función recursiva $ \pi:(\chi_i)^m\rightarrow\{0,1\}$ para determinar, a partir de una secuencia finita de $ m$ configuraciones globales que $ t_0$ ha ocurrido, es decir:
    $\displaystyle \pi(c_t,c_{t+1},\cdot,c_{t+m-1})=1\;ssi\;t=t_0$
    Este procedimiento $ \pi$ sirve para detectar el final de un cálculo, y sucede cuando se ha encontrado una configuración en particular.
Ahora, $ Z$ es un espacio celular computación-universal si existe un conjunto de configuraciones globales $ U\in Z$ tal que para cualquier función parcial recursiva (enumeración de configuraciones globales) $ g$ , efectivamente se puede encontrar una configuración global $ c\in U$ tal que $ c$ calcula $ g$ .

Se requieren de los espacios celulares para simular otros dispositivos de cómputo tales como las máquinas de Turing. En general un sistema lógico de manipulación de cadenas es uno que toma como dato de entrada una cadena $ S$ , y obtiene a su salida a lo más otra cadena $ S'$ (posiblemente $ S=S'$ ) que puede ser obtenida de $ S$ en un solo paso. De manera que si se ven las configuraciones globales como cadenas de símbolos, la función de transición global es un sistema lógico de manipulación de cadenas.

Una generalización directa al espacio de $ d$ -dimensiones del concepto de cadena, es un patrón. Así un patrón en 1-D es una cadena, y una configuración con soporte finito en un espacio celular $ d$ -D es un patrón $ d$ -D. Entonces un espacio celular es un sistema monogénico, es decir, de manipulación de patrones, como también lo son las máquinas de Turing o el sitema tag de Post.
Un sistema de manipulación de patrones $ T$ es un par ordenado $ (P,v)$ , donde $ P$ es un conjunto de patrones finitos indizados con números enteros, y $ v:\mathbb{N}\to\mathbb{N}$ es una transformación de patrones. Ahora, consideremos un espacio celular $ Z$ y un sistema de manipulación de patrones $ T$ . Sean además, $ k_1$ y $ k_2$ números enteros positivos, $ i$ el índice de los patrones en $ P$ y $ \mathbb{C}$ el conjunto de todas las configuraciones en $ Z$ con soporte finito, es decir, configuraciones globales definidas en espacio celular finito. entonces $ Z$ simula $ T$ en $ \frac{k_2}{k_1}$ evoluciones si y sólo si existe una función inyectiva y computable $ \gamma:\mathbb{N}\to\mathbb{C}$ y existe también una función $ \delta$ de funciones recursivas sobre funciones recursivas tal que:
$\displaystyle F^{k_2}(\gamma(i))=\gamma(v^{k_1}(i)); \textrm{ donde $F=\delta(v)$}$

De manera que una máquina de Turing se puede describir en función de configuraciones globales de autómatas celulares, dando un conjunto $ P$ de ``descripciones instantáneas'' y una función $ v$ que está determinada por la función ``siguiente estado'' del control de la cabeza lectora de la máquina de Turing. Se ha supuesto que cuando la máquina de Turing termina, la secuencia asociada de patrones continúa pero es pasiva ($ v(i)=i$ ).
Alvi Ray Smith III introduce el concepto de $ (m,n)-$ Turing machine, que es una máquina de Turing que especifica el par $ (m,n)$ , y se refiere a la tabla de símbolos-estados como lo muestra la tabla 1.3


Tabla 1.3: Tabla de símbolos y estados. $ X\in \{ R, L \}$ , $ 0\leq i\leq (m-1)$ , $ 0\leq j\leq (n-1)$

$ q_0$ $ q_1$ $ \cdots$ $ q_{n-1}$
$ s_0$



$ s_1$



$ \vdots$

$ \frac{x_iX}{q_j}$
$ s_{m-1}$




Alvi Ray Smith III demostró que cualquier máquina de Turning (m,n) $ T$ , se puede simular con un autómata celular $ 2D$ de tamaño $ \max(m+1,n+1)$ , una vecindad de 7 células; con lo que establece una relación entre las evoluciones de los autómatas celulares que menciona en ese teorema y los cálculos en las máquinas de Turing.
Image arsNeigb
Figura 1.6: Modelo de vecindad creado para hacer computación universal


La geometría del espacio de vecindades se usa para poder distinguir una célula en estado $ Q_1\in A=\{1,\cdots,m\}$ que corresponden a un símbolo de la máquina de Turing, de una célula en estado $ Q_2\in B=\{1,\cdots,n\}$ que corresponden a un estado de la máquina de Turing.
La manera en que este autómata celular simula una máquina de Turing $ T$ , es que sus evoluciones asemejan el comportamiento de la máquina $ T$ . El autómata celular diseñado por Ray Smith III es entonces definido en un espacio bi-dimensional, dedicando un renglón de células para simular la ``cinta'' de la máquina de Turing, una célula del espacio celular corresponde a un cuadro en la cinta, y un renglón del espacio celular se dedica a los movimientos de la cabeza lectora de la cinta. Las células del otro renglón están en estado nulo $ Q_0$ .
Es interesante la comparación entre las pruebas de computabilidad universal hechas por von Neumann, Codd, Arbib que se basan en el modelo original de von Neumann y por otro lado el modelo que Ray Smith propone; es interesante porque la diferencia radica en que, en el modelo de Ray Smith el diseño del autómata celular depende de la máquina de Turing a ser simulada; y desde el punto de vista de los modelos basados en la idea de von Neumann, cualquier máquina de Turing se puede simular una vez que el diseño del autómata celular ha sido propuesto.
Sin embargo, la diferencia entre los autómatas celulares (dependientes de la máquina de Turing e independientes de la máquina de Turing) ya no es importante cuando la máquina de Turing que se va a simular es precisamente la máquina universal.
Se puede traducir el autómata celular de dos dimensiones definido originalmente por Ray Smith, en un autómata celular de una dimensión, también definido por él mismo. La configuración de vecindad en este nuevo autómata celuar 1D se muestra en la figura 1.7-a. En la figura 1.7-b se muestra cómo están distribuidas las células del antiguo espacio celular bidimencional en el nuevo espacio celular lineal.

Figura 1.7: a) Modelo de vecindad creado para hacer computación universal en 1D. b) configuración de la máquina de Turing relacionada. c) Segundo ejemplo de una máquina de Turing relacionada a un espacio celular 1D.
Image cu1d_ars

El trabajo de Ray Smith incluye el siguiente enunciado: Para cualquier máquina de Turing $ T$ $ (m,n)$ , existe un espacio celular $ Z_T$ de 3 vecinos y un espacio de estados de $ (m+2n)$ que simula computación universal (figura 1.7-c). El razonamiento para validar la declaración anterior es dar un espacio celular $ Z_T$ con la configuración de vecindad de adecuada y un diseño de máquina de Turing como se muestra en la figura 1.7-c. La función de transición $ f$ no cambia el estado de las células, excepto en los casos $ a$ , $ h$ y $ s$ . Se pueden completar de manera más o menos sencilla los detalles de la función de transición para que las configuraciones de la cinta $ \cdots x_0x_1qx_2x_3\cdots$ se muevan a la derecha ($ L$ ) y tener el nuevo estado $ q'$ y cambiar el símbolo $ x_2$ a $ x_2'$ :


$\displaystyle {\cdots x_0x_1qx_2x_3\cdots}$
$\displaystyle {\cdots x_0x_1x_2'q'x_3\cdots}$
Similarmente el movimiento a la izquierda tendría el siguiente aspecto:


$\displaystyle {\cdots x_0x_1qx_2x_3\cdots}$
$\displaystyle {\cdots x_0x_1q_L'x_2'x_3\cdots}$
$\displaystyle {\cdots x_0q'x_1x_2'x_3\cdots}$
Los estados $ q$ y $ q_L$ se necesitan para representar cada estado de la máquina de Turing. En este caso, el símbolo nulo es simulado por el estado nulo.
Finalmente, en el trabajo se muestran las condiciones necesarias para que un autómata celular desarrolle computación universal. En particular, se muestra que es suficiente un autómata celular en 1D para hacer computación universal en el dominio de las funciones parciales recursivas. Un autómata celular capaz de hacer computación universal se llama espacio celular computación universal. El trabajo de Ray Smith III ha servido para obtener algunos resultados que se aplican al usar autómatas celulares como generadores de lenguajes.