| 1. Complexity |
|
|
2. Bi-regular graphs |
|
|
3. Finite graphs |
|
|
4. Dimension 1 |
|
|
5. Symbolic dynamics |
|
|
Publications |
There are several ways of
measuring the complexity of a system. One of them is to study its
computational power, i.e., the kind of calculation that can be
done through its dynamics. Roughly speaking, the main result we obtained
for the ant, in bi-regular graphs of degrees 3 and 4 (which include the
square and the hexagonal grids), was that its dynamics may perform
the same calculations of a computer (if the appropriate initial
configuration is provided) [1,2].
In other words, it is 
computationally universal. The way to show it was the following.
First, we designed graphs on which the dynamics of the ant had the
effect of performing a logical operation on Boolean values written
in the cells. The next step was to find configurations in the
square grid that could reproduce the trajectories that had been
designed in ad-hoc graphs. We had to be able to fix paths
for the ant, to cross these paths, and to join different paths
in a single one.
The first configurations that met these requirements were found through intensive (computer-aided) exploration of possible configurations and of the sites that the ant used to go in and out of them. Later, general designs were done for crossings and junctions, which can be implemented in any bi-regular graph of degrees 3 or 4, allowing the construction of logical circuits [2]. The scheme on the left shows a "NOT" device. On the right we show the embedding in the square grid of the gate that crosses two signals (variables). The cells with the initial values of the input variables are in the top row. The cells that will contain the results of the Boolean operation, when the ant has traversed the configuration, are in the bottom row.
This construction has several consequences. First, the prediction of the result of a Boolean circuit, given its inputs, is known to be a P-complete problem. The P-hardness of the following problem can be derived from this: for a given configuration and two given cells, decide whether or not the ant visits one of them before visiting the other. On the other hand, by drawing a circuit that calculates the rule of a one-dimensional cellular automata with a quiescent state, we can put the ant to reproduce the dynamics of a Universal Turing Machine. This implies the computational universality. More precisely, what we obtained was an infinite, periodic configuration of the grid, in which only a finite perturbation is required to write the "program"; then the ant, in its walk, will execute it in succesive rows, drawing the space-time diagram of the cellular automata and perfoming the programmed calculation, forever. By the way, we obtain the existence of undecidable questions about the dynamics of the ant (due to the existence of such questions for cellular automata and Turing machines).
case. More precisely: starting at a given position,
there are large areas of the graph which the ant cannot reach. The succesive
application of this restrictions shows that for finite initial configurations,
the ant will always eventually start building a staircase of some kind
(this, as we know, does not happen on the hexagonal grid, and is
believed to happen in the square grid). One of the consequences of this is
that the dynamics of the ant can be predicted for finite initial configurations.
And even if the initial configuration is not finite, the behavior of the
ant turns out to be very simple, as shown by results obtained in the
subject [5].
There are also important differences between the bi-regular graphs of degrees 3 and 4. Whereas for graphs of degree 4 (or greater) the trajectory of the ant is always unbounded, for graphs of degree 3 there is an infinity of initial configurations that lead to periodic (bounded) trajectories. Another special feature of graphs of degree 3 (and this holds for non bi-regular graphs too) is the symmetry observed for some initial configurations. It is shown that for a certain class of configurations, the ant returns systematically to the starting point, and if, in addition, the initial configuration has bilateral symmetry, then this symmetry is recovered each time the ant comes there. [4]
the trajectory is a simple chain, and is therefore linearly bounded
by the diameter of the graph. In a bigger class, that of the planarly
represented graphs without strings in their cycles,
the period of the trajectory of the ant is still linearly bounded in
the size of the graph. If the restriction of planar representation is
dropped, then there are families of graphs (even without strings in their
cycles) where the period grows exponentially with the size of the graph;
on the other hand, if strings are allowed in the cycles, then there
are, too, simple examples of exponential growth (the graphs are in fact
outerplanar subgraphs
of the square grid). The last result was the construction of Boolean circuits;
as we said above, this work was then carried over to the regular grids.
 |
 |
 |