| 1. Complejidad |
|
|
2. Grafos bi-regulares |
|
|
3. Grafos finitos |
|
|
4. Dimensión 1 |
|
|
5. Dinámica simbólica |
|
|
Publicaciones |
Existen diversas formas de evaluar
la complejidad de un sistema. Una de ellas es estudiar su capacidad
de cómputo, es decir, el tipo de cálculo que se puede
realizar a través de su dinámica. A grandes rasgos, el resultado
principal obtenido para la hormiga, en grafos bi-regulares de grados 3
y 4 (lo que incluye la malla cuadriculada y la hexagonal) fue que su dinámica
puede realizar los mismos cálculos que un computador (con la
configuración inicial apropiada) [1,2].
Es decir, es
computacionalmente
universal. La forma en que se llega a esto es la siguiente. Primero,
se diseñaron grafos en los que la dinámica de la hormiga
tuviese el efecto de realizar una operación lógica entre
valores booleanos escritos en las celdas. El paso siguiente fue encontrar
configuraciones en la malla cuadriculada que permitiesen reproducir en
ella las trayectorias que se habían diseñado en un grafo
general. Esto implicaba poder fijar caminos para la hormiga, poder cruzar
esos caminos, y poder reunir distintos caminos en uno sólo.
Las primeras configuraciones para ese fin se encontraron explorando intensivamente (con el computador) las configuraciones posibles, y los sitios por los que la hormiga entraba y salía de ellas. Más tarde se realizó un diseño general para los cruces y las uniones, que puede ser implementado en cualquier grafo bi-regular de grado 3 ó 4, permitiendo construir en ellos circuitos lógicos [2]. El esquema de la izquierda muestra la forma de diseñar un "NOT". El de la derecha, muestra como la puerta que cruza dos señales pudo escribirse en la malla cuadriculada. En la fila superior se encuentran las celdas que contienen los valores iniciales de las variables de entrada, y en la fila inferior están las celdas que contendrán la evaluación de la puerta lógica una vez que la hormiga haya atravesado la configuración.
Las consecuencias de la construcción son varias. En primer lugar, la predicción del resultado de un circuito booleano, dadas sus entradas, es un problema P-completo, de donde se puede derivar la P-dureza del problema de determinar, para dos celdas dadas en una configuración, acaso la hormiga visita una de ellas antes que la otra. Por otro lado, a través de un circuito que calcule la regla de un autómata celular unidimensional con estado quiescente, es posible hacer que la hormiga reproduzca la dinámica de una máquina de Turing universal. Esto implica la universalidad de cómputo. De manera más precisa, lo que se obtuvo es una configuración infinita, periódica, de la malla, en la que se introduce una perturbación finita que representa el "programa"; luego la hormiga, al andar, lo ejecuta en líneas sucesivas, dibujando el diagrama espacio-temporal del autómata celular y realizando así el cómputo deseado, hasta el infinito. De paso, se obtiene la existencia de preguntas indecidibles respecto a la dinámica de la hormiga (debido a la existencia de tales preguntas respecto a los autómatas celulares y máquinas de Turing).
clase), con grandes restricciones. Más precisamente: desde una posición
dada, hay vastas áreas del grafo que resultan inalcanzables para
la hormiga. La aplicación sucesiva de estas restricciones permite
demostrar que para configuraciones iniciales finitas, la hormiga siempre
terminará por empezar a hacer un tipo de escalera (lo que, como sabemos,
no ocurre en la malla hexagonal, y parece ocurrir en la cuadriculada).
Esto implica, entre otras cosas, que la dinamica de la hormiga es
previsible en configuraciones iniciales finitas. Además, aun si la configuración
inicial no es finita, el comportamiento de la hormiga se muestra fuertemente
"simple", como lo muestra el estudio realizado en el tema 5.
Los grafos bi-regulares de grados 3 y 4 se diferencian fuertemente también. Mientras en los grafos de grado 4 (o superior) la trayectoria de la hormiga es no-acotada para cualquier configuración inicial, en los grafos de grado 3 se encuentra una infinidad de configuraciones iniciales que dan lugar a una trayectoria periodica (o acotada). Otra gran particularidad de los grafos de grado 3 (y el resultado es valido no solo para grafos bi-regulares) es la simetría observada para algunas configuraciones iniciales. Concretamente, se demuestra que para una cierta clase de configuraciones iniciales la hormiga vuelve sistemáticamente al punto de partida, y que si la configuración inicial tiene ademas simetría bilateral, ésta se mantendra a cada vuelta de la hormiga [4].
sencillo, el de los árboles, la trayectoria es una simple
cadena, y por lo tanto el período está acotado linealmente
por el diámetro del grafo. En una clase un poco mayor, la de los
grafos sin cuerdas en sus ciclos, representados planarmente, el
período aún podía acotarse linealmente en el tamaño
del grafo. Pero ya eliminando esa restricción de representación
planar aparecen familias de grafos en que el período crece exponencialmente
con el tamaño; asimismo, para grafos con cuerdas en sus ciclos,
representados planarmente, se encontraron ejemplos sencillos en que esto
ocurre (de hecho, se trata de subgrafos de la malla cuadriculada). Lo último
que se hizo fue la construcción de circuitos lógicos;
como se dijo más arriba, ese trabajo se traspasó luego a
las mallas regulares.
 |
 |
 |