A Double-Sieve Method to Identify Emergent Computation in Cellular Nonlinear Networks

Cellular nonlinear networks (CNN) and cellular automata have found numerous applications in fast multidimensional signal processing. As a new computational paradigm, the main problem is associated with "design for emergence" i.e. with the identification of proper cells such that the resulting model will perform certain useful computation (e.g. pattern recognition, feature extraction, compression, self-reproduction, modeling of biologic phenomena, etc). This is a very difficult problem due to the huge search space (e.g. there are 2⁵¹² possible Boolean cells with 9 inputs). This paper introduces a novel and effective method, capable to evaluate a large family of CNN cells and provide a list containing only a few interesting cells, leading to emergent behaviors that may find computational applications. The method is based on the successive use of two "sieves", each sieve being tuned to certain parameters indicating to what extent the dynamic behavior is emergent. The first sieve is tuned to the transient length and clustering coefficient while the second is tuned to select behaviors with a certain type of front wave propagation in the array of cells. The method outperforms any other methods to isolate emergent computation and reveals a wide palette of interesting behaviors