Effective and robust nanoscale computation will require large numbers
of simple component devices that can be densely packed, locally
connected, and can perform sophisticated information processing with
high parallelism, robust operation, and no central control. Cellular
arrays are a natural architecture for fulfilling these requirements,
and, due to their regular structure, are amenable to molecular
self-assembly techniques.
While there has been tremendous progress on building nanoscale
devices, there has been less progress on programming and combining
these devices to produce useful computation. Cellular array
architectures such as cellular automata and cellular non-linear
networks have been proved to be capable of universal computation.
However, these proofs simply demonstrate that classical, serial,
Boolean logic gates or Turing machines can be (laboriously) simulated
by cellular arrays, and do not suggest practical ways to program these
devices in efficient ways that take advantages of their parallelism
and potential robustness.
We believe that a more powerful and ultimately practical approach is
to harness the ability of cellular arrays to form complex patterns in
ways that will produce decentralized collective information
processing. This approach to information processing is very different
from classical approaches, and will require non-standard programming
and analysis techniques.
The objective of this project is to develop such techniques. In
particular, we are investigating evolutionary computation, and in
particular,
coevolutionary learning as a method for "programming" cellular
arrays to perform computations, and to investigate analysis techniques
that build on both pattern dynamics and classical computation theory
for understanding the computations in such arrays. We are also
extending our studies beyond the idealized cases of noise-free systems
with perfectly synchronous updating and periodic boundary conditions,
and to investigate the "real-world" requirements of dealing with
asynchronous updating, unreliable components, and non-periodic
boundary conditions.
|
|
Figure 1: Behavior of a CA evolved by the GA for the density classification task. (a) Initial configuration is low-density (majority white). CA correctly goes to fixed-point of all white. (b) Initial configuration is high-density (majority black). CA correctly goes to fixed-point of all black. (c) Regular regions of (b) are filtered out, leaving particles. (d) Catalog of all possible particles, particle velocities, and interactions for this CA. |
The work proposed here builds on our previous research on one-dimensional cellular automata (Crutchfield & Mitchell, 1995; Mitchell, Crutchfield, & Das, 1996). We used a genetic algorithm (GA) to evolve radius-3 CA rules with synchronous updates and periodic boundary conditions to perform two tasks, density classification and synchronization, that require collective computation. Figure 1a-b gives space-time diagrams illustrating the behavior of one of the evolved CAs for the density classification task on both a low-density and high-density initial configuration. The space-time diagrams exhibit three types of regions (domains) described by simple regular languages: all 0s (white), all 1s (black), and alternating 1s and 0s (checkerboard pattern, appearing as gray area in this low-resolution figure).
Because the task requires computational power equivalent to a context-free language, the relevant features of the computation are the boundaries between regular domains, here called "particles" (Hanson and Crutchfield,1993). Figure 1c shows the particles that are embedded in Figure 1b. As viewed in Figure 1c, particles are coherent structures that propagate in space and time. Figure 1d lists all the types of particles that this CA can form, their velocities, and their possible interactions (collisions) with one another. This table, in effect, gives the "laws of particle physics" in the small "universe" defined by this CA.
To understand how this CA performs the density classification task, we can identify particles as information carriers, and collisions between particles as the loci of information processing. This framework has been shown to formally characterize computational behavior of such cellular automata (Hordijk, Crutchfield, & Mitchell, 1996). In short, particles and particle interactions form a high-level language for describing computations in spatially extended systems such as CAs, and for predicting the results of those computations.
In recent work, we investigated "coevolutionary" learning, in which the CAs and the test initial configurations coevolve to challenge one another. We found that such coevolution dramatically improves success of the genetic algorithm (Pagie & Mitchell, 2002; Mitchell, Thomure, & Williams, 2006).
References: