Cellular Nonlinear Networks: State of the Art and Applications - Systematic Design for Emergence in Cellular Nonlinear Networks - page 7

2

Cellular Nonlinear Networks: State of the Art
and Applications

2.1 Introduction

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 para-
digm called cellular computing. The structure of such a computing system is de-
fined 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.
The cell assumes an initial state and may have one or more external inputs. In a
cellular system, computation can be considered any form of meaningful emergent
global phenomenon resulted from a proper design of the cell. Usually the initial
state and the inputs code the problem to be solved while the answer to this prob-
lem is coded in an equilibrium state. For instance, in the character segmentation
example provided in Chap. 8, the initial state contains a visual field with black/white
pixels (e.g. handwritten figures) while the steady state result of the emergent dynam-
ics is a collection of rectangles, each enclosing a compact handwritten character.
More complicated dynamics (e.g. oscillatory or chaotic) can also encode a solution
to the problem posed as initial state. This is the case when cellular systems are used
to generate pseudo-random sequences, a widely known application of the cellular
systems.
The first cellular computers were theoretical constructs introduced by Stanislaw

,

M. Ulam in the 1950 s [18]. He then suggested John von Neumann to use what he

called “cellular spaces” to build his self-reproductive machine [19]. Konrad Zuse
(who built the first programmable computers between 1935-1941) was the first to
suggest that the entire universe is being computed on a computer, possibly a cellu-
lar automaton (CA) [16]. Many years later similar ideas were also published by
Edward Fredkin [20,21] and recently (2002) by Stephen Wolfram [17]. In 1982
Fredkin and Toffoli published a paper [22] where cellular computation based on