Search

Cellular automata were long recognized as having a great potential for applications, particularly when one have to deal with multi-dimensional signal processing or modeling. One of the main obstacle was to design CAs, i.e. to select among many possible cells the ones having a desired behavior. Usually such cells were randomly selected and the corresponding CA simulated. Then one would associate certain uses to that particular CA. Not surprisingly, one of the first application of CA is the random number generator, a behavior which can be characterized, in the light of the measures defined in the previous chapters, as a behavior with a large exponent of growth and a clustering coefficient around 0.5. As seen from our investigations over large families of semi-totalistic cells, there are many CAs with the above characteristics. Therefore a random selection of CA cells will likely provide a good number generator. [ABSTRACT FROM AUTHOR]

Solving some of the open problems using the principles of natural computing exposed in the previous chapter led to the idea of developing a computing paradigm called cellular computing. The structure of such a computing system is defined by a grid (often two-dimensional) of locally interconnected cells. Each cell may be in a number of states (ranging from 2 to infinity) and the state of a cell depends by its own previous state and the previous states of its neighbors through a nonlinear functional, which may be defined in different ways. This functional is associated with a practical implementation of the cell and includes a set of tunable parameters grouped as a gene vector [7]. By tuning the gene parameters one can achieve programmability, i.e. different emergent behaviors within the same basic cellular architecture. [ABSTRACT FROM AUTHOR]

In Chaps. 4 and 5 several measures for emergence were introduced and as seen in Chap. 6 they can be integrated in an intelligent sieving process to select among a huge number of possible cells only those leading to CA dynamics that is meaningful for certain desired tasks. Still, evaluating the measures of emergence needs extensive running of the CA system for each member of the family, giving thus important limitations in terms of computing time. While the CA is mainly determined only by the cell structure (assuming that all cells are identical) and by the interconnection between cells (also assumed to be regular and simple) it would be reasonable to investigate the possibility to predict the CA behaviors solely based on the structure of the cell. That will dramatically reduce the computation time eliminating the need to simulate the entire CA. [ABSTRACT FROM AUTHOR]

In the previous chapter several scalar complexity measures (the clustering coefficient, its variance and the transient length) were introduced to characterize a given cellular automata system from the point of view of its behavior and likelihood of emergent phenomena. These were the first steps in establishing a set of methods called design for emergence. [ABSTRACT FROM AUTHOR]

So far we introduced and discussed four nearly-orthogonal measures of emergence (the exponent of growth, the variance, the transient length, and the clustering coefficient) capable to give a synthetic description of the emergent behavior in a cellular array (CA, CNN or Small Worlds network) with a given cell (usually specified by its family name and the particular ID). [ABSTRACT FROM AUTHOR]

Natural computing was recently defined as a novel paradigm for computation where nature is taken as an example to define computational architectures and algorithms capable to solve problems efficiently and while being based on a low complexity description of its structure. A living being can be considered as performing various natural computation tasks. While exhibiting complexity in performing various functional tasks (pattern recognition, decision, orientation, optimization, planning, creative thinking, self-repair and self-reproduction, to name just a few) it is assumed that the entire development of the being is encoded within its genome. Due to recent progress in mapping the entire human genome, it is widely accepted that such a genome contains no more than several megabytes of information stored in the strings of DNA, being even simpler for more primitive species. Thus, in a simplified approach, the entire behavioral complexity of a living being can be regarded as being encoded in a relatively compact information storage structure, the DNA. This is what we will call structural information, i.e. the minimal information required to construct a computational architecture. [ABSTRACT FROM AUTHOR]

Cellular computing systems hold the potential of modeling and understanding of complex aspects of our world. So far the CNN paradigm [7], which integrates the cellular automata (CA) as a special case, offers a unified framework to understand complex emergent behaviors and to apply them in real world applications. [ABSTRACT FROM AUTHOR]

The main features of cellular systems are regularity and homogeneity. In fact a cellular system can be defined as a structured collection of identical elements called cells. The structure of a cellular computing system is given by the choice of a lattice. Such lattices are one-dimensional, two-dimensional and, less used, three or more dimensional. The following are examples of commonly used two-dimensional lattices [ABSTRACT FROM AUTHOR]