Документ взят из кэша поисковой машины. Адрес оригинального документа : http://polly.phys.msu.ru/~rambidi/image%20processing%201.pdf Дата изменения: Mon Nov 21 19:27:34 2005 Дата индексирования: Mon Oct 1 21:09:12 2012 Кодировка:

Int. Journ. of Unconventional Computing, Vol. 1, pp. 000-000 Reprints available directly from the publisher Photocopying permitted by license only

© 2004 Old City Publishing, Inc. Published by license under the OCP Science imprint, a member of the Old City Publishing Group

Biologically Inspired Information Processing Technologies: Reaction-Diffusion Paradigm
NICHOLAS G. RAMBIDI
Physics Department, Moscow State University, Leninskie Gory, 117234 Moscow, Russia (Received February 22, 2004; In final form April 21, 2004)

Chemical reaction-diffusion media represent information processing means capable to efficiently solve problems of high computational complexity. Distributed character and complex nonlinear dynamics of chemical reactions inherent in the medium is the basis of large-scale parallelism and complex logical operations performed by the medium as primitives and equivalent to hundreds of binary fixed-point operations. Photo-sensitive catalysts controlling the dynamics (modes of functioning) of the medium enable to easily perform input of initial data and output of computational results. It was found during the last decades that chemical reaction-diffusion media can be effectively used for image processing, finding the shortest paths in a labyrinth and solving some other problems of high computational complexity. Spatially non uniform control of the medium by physical stimuli and fabrication multi level reaction-diffusion systems seem to be promising way enabling low cost and effective information processing devices that meet the commercial needs.
Key words: biomolecular computing, computational complexity, reactiondiffusion media, image processing

SEVERAL POINTS OF DEPARTURE The importance of biologically inspired information processing technologies is often taken for granted nowadays. In point of fact, their development has been virtually and continues to be far from real practical
Corresponding Author: E-mail: rambidi@polly.phys.msu.ru

1


2

RAMBIDI, et al.

applications. However, it is these technologies that would become the viable breakthrough if they enable high-performance information processing means of low commercial mass production costs. Just as they could be highend devices but capable to solve very complicated problems inaccessible to modern von Neumann computers. The understanding of this situation seemed to be the starting point for the awakening of the interest to technical engineering approaches that use biological objects for the elaboration information processing means. The most promising between them is the conception of amorphous computing offered lately [1] and supported by the official agencies of US Government [2]. It is based on several practical ways to elaborate fundamentally new devices including practical implementation of unique information processing features of distributed biological, biochemical and chemical reaction-diffusion media. It should be mentioned that several important experimental investigations of information processing features of chemical reaction-diffusion media were performed during the last couple of decades [3-15]. They manifested that these media were capable of ef fective solving problems of high computational complexity including image processing, finding the shortest paths in a labyrinth, and some other important physical problems. This paper was designed as an attempt to estimate practical opportunities to elaborate operational information devices based on results of these investigations. Fantastic progress of information processing means during the second half of the last century was launched in early forties by John von Neumann. General principles inherent in his paradigm proved to be indispensable for the elaboration of multipurpose computing systems that was capable of optimally solving different, mostly engineering problems. It is important to mention here that mathematical and computational basis for these projects could be reduced mostly to the problems of rather low (polynomial) computational complexity. During the second half of the last century the character of computational complexity of problems inherent in practical projects was virtually of decisive importance for the choice of the paradigm used for the elaboration of new computing means. And for the couple of last decades in essence, human society has had to face increasingly complex computational problems that are inherent in understanding and controlling important complex processes in economics, social sciences, pollution control, and so on. The point is that, in spite of the tremendous progress of contemporary digital computers, they did not prove to be efficient for solving problems of high computational complexity. And the question is until now which way is more advantageous for further information processing development:


REACTION-DIFFUSION PARADIGM

3

- to increase enormously the computational performance of contemporary digital semiconductor computers, or - to elaborate information processing means fundamentally different from von Neumann ones and capable of solving efficiently problems of high computational complexity? Attempts to increase the computational performance of digitals computers were based during the last decades mainly on micro miniaturization of planar semiconductor IC's. Nowadays these devices are close to the physical limit as a result of the huge progress in this field. Therefore a lot of attempts to find the real alternative to semiconductor technology were performed. One of the most promising between them is biological paradigm based on mechanisms of information processing by biomolecular and biological entities (see, for instance, [16]). The first steps in this direction were made several decades ago. In early forties, nearly simultaneously with the advent of von Neumann paradigm McCulloch and Pitts [17] offered a principally different approach to designing information processing devices. According to the ideas of McCulloch and Pitts [17] computational system is designed to be in a sense analogous to human brain. Simple processors (neurons) are constituent parts of the system and each of them is connected to all other processors in some definite manner. Computing capabilities of the system are defined by the predetermined complex structure of the system (that is by character of neuron connection), not by the stored program. Problems are solved by the system with very high degree of parallelism. At the same time the character of dynamics inherent in the system defines the storage of information and information processing capabilities of the system. McCulloch and Pitts [17] used two fundamental principles of information processing by biological entities laying in the basis of the neural net approach. They are: - "all or none" mode of a single neuron activity, that is nonlinear dynamic mechanism, - large-scale parallelism of neural connections in a neural net. During the following decades (1950s-1970s) there was intense discussion on the information processing capabilities of those systems (see details in [18]). Principles of designing neural nets capable of solving predetermined problem were analyzed in detail. Theoretical possibilities to train the net that enable to design net structure optimal for solving chosen problem were discussed. Contemporary neurocomputers have proved to be a practical result of


4

RAMBIDI, et al.

these theoretical investigations. Regretfully the theoretical basis of "hardware" development that is of material implementation of neural nets was not practically under consideration till now. And therefore designers of neural net devices used the most habitual, "making a road smooth" way - the utilization of planar semiconductor circuitry and technology, which proved to be fantastically suitable for the implementation of discrete von Neumann devices. It should be mentioned that there is virtually no alternative now to discrete circuitry and technology for the implementation of neural nets. It is easy to understand the roots of this situation. The point is that planar semiconductor technology supplanted all offered earlier realizations due to its manifest advantages. Hardware implementation of neural nets based on semiconductor digital circuitry faces considerable and most likely principal difficulties, such as large-scale integration limits, functional and processing speed limits, and the "nightmare of interconnections". Typical semiconductor chip has rigid structure. Removing even one of its primitives (or changing its characteristics) makes in general case the chip disabled. Known biological systems capable of information processing (and having often neural net architecture) are built from initial molecular fragments dif ferent fundamentally from semiconductor primitives. One of the basic and probably the most important features is structural redundancy. Biopolymer enzyme molecules play important role in information processing by biological systems. The structure of enzyme molecule represents a combination of a functional molecular fragment and lengthy polypeptide tail. The remarkable property of this structure is that removing even rather big part of this tail leads to inessential small changes of enzyme function. Another important type of redundancy is inherent in distributed reactiondif fusion media. Reaction-dif fusion media are continuous extended physical, chemical or biological systems enabling high behavioral complexity. The dynamics of these systems can be described by a set of differential equations:

where: the first term in the right side of the equation describes nonlinear dynamics (kinetics of the chemical reactions proceeding in the system), the second one corresponds to diffusion of the system components. As a rule the phase diagram corresponding to reaction-dif fusion


REACTION-DIFFUSION PARADIGM

5

equations has a number of basins of attraction. Moving the point inside the space of the basin does not lead to changes of dynamic regime (that correspond to the moving to another basin of attraction). This feature can be defined as dynamic redundancy. In common case the redundancy is the basis for variation of object characteristics and selection. System built from such objects seems to be capable of learning and adaptive behavior. Structural and especially dynamic redundancy discussed below are fundamental features of biologically-inspired information processing.

OPERATIONAL FEATURES OF DISTRIBUTED REACTION-DIFFUSION MEDIA Complex nonlinear dynamic mechanisms determine behavior of biological, biochemical, and chemical objects at dif ferent levels of organization. Sophisticated oscillatory processes in a human brain are known at the tissue level. Heart rhythm disturbances and sudden death phenomenon are determined by pathological modes of myocardium excitation [19]. Complex dynamic regimes lead to the ordered spatial evolution at the level of cell assemblies, for instance, to formation of non uniform circular cell distributions in thin layers of Dictyostellium Discoideum [20], and Salmonella Typhimurium [21] Concentration oscillating modes, trigger regimes and dissipative structures were found for divers chemical and biochemical reactions in biological membranes and cells, that is at supramolecular level [22]. And finally complex dynamics could be the origin of collective excitations in biomacromolecules, at the molecular level [23]. All of these systems could be used for the experimental investigation of nonlinear phenomena. Nevertheless, media used for practical applications should be available, stable, and handy. Chemical reaction-diffusion media (see below) satisfy to these demands. It has been recognized during the last decades (see, for instance, [24]) that the variety of dynamic regimes inherent in reaction-diffusion system enables to use them for information processing. Distributed reactiondiffusion media could be the material basis for information processing devices based on fundamentally different from von Neumann principles. They comprise: - natural large-scale parallelism, - nonlinear mechanisms of information processing, - multilevel architecture.


6

RAMBIDI, et al.

Large scale parallelism Reaction-diffusion medium performs information processing operations in each micro volume (see below) simultaneously according to some algorithm the same for each micro volume. This algorithm is determined by the chosen state of the medium (concentrations of the medium components, temperature and some other physical stimuli). Typical linear size of micro volume is about 0.01-0.1 mm. Therefore the level of parallelism corresponding to the most primitive device (pseudo flat layer of the reagent, the size 100?100 mm) is 108-106. The level of parallelism could be greatly increased due to three-dimensional shape of the medium. High logical complexity of primitive operations Nonlinear dynamic mechanisms inherent in to distributed reactiondiffusion media cause large-scale logical complexity of primitive operations performed by the medium instead of binary ones typical for von Neumann computers (see below). Consider, for instance one of the simplest of them, that is a contour enhancement of arbitrary graphical object (black figure on the white background). Suppose that the shape of the object is simple enough and the resolution of the picture equal to 10 3 ?10 3 points is satisfactory for adequate numerical contour enhancement by contemporary digital computer. Typically, about 3-5 floating point operations are necessary to enhance the contour. Therefore the number of operations of the digital computer ~ 3?106 is equivalent in this case to one primitive operation of the reaction-diffusion medium. If the contour of the image is complicated and the resolution 10 4?10 4 or even 10 5?10 5 is necessary, one primitive operation of the reaction-diffusion medium is equivalent to ~108 or ~1010 floating point operations. Therefore the fundamental feature of reactiondiffusion information processing media is that information processing capability increases when the complexity of the problem grows. Key attributes of reaction-diffusion information processing Reaction-dif fusion media enable to realize fundamentally new approaches to elaboration of information processing devices. High computational power in this case is due to large-scale logical complexity of primitives, not due to high computational speed caused by high level of micro miniaturization. The fundamental and important information processing feature of the reaction-diffusion medium is that it is an instance machine [25], i.e., the opposite extreme of a universal computer and represents an information


REACTION-DIFFUSION PARADIGM

7

processing device that encodes a single problem instance in its structure. There are two basic properties typical for an instance machine: - the physical structure of the machine is specific for a single problem instance, - the temporal evolution of the machine leads, under conditions predetermined by the problem under solution, to a state or structure that can be interpreted as a solution of this problem. A r eaction-dif fusion processor based on nonlinear dynamic mechanisms is the instance machine. The solution of a single problem is determined by an appropriate state of the medium (composition, temperature) and control stimuli. It should be mentioned here the importance of instance machine conception for the understanding of the essence of biologically inspired information processing technologies. The point is that in nature one can hardly observe universal computing realizations but more instant machines (dynamics of ant populations, nonlinear phenomena in heart tissues and so on).

INFORMATION PROCESSING IN BEIOUSOV-ZHABOTINSKY MEDIA Chemical and biochemical distributed reaction-dif fusion systems (particularly BeIousov-Zhabotinsky (BZ) media [26]) are promising bases for fabrication of information processing means capable to effectively solve problems of high computational complexity. They seem to be able to meet the requirements of next-generation information systems, such as robustness, resilience, diversity, and scalability. Robustness The BeIousov-Zhabotinsky type reaction is a catalytic oxidation of some organic substance (mainly malonic acid) by potassium bromate or some other oxidizing agent. The mechanism of this process is complex. It is determined by a nonlinear kinetics of intermediate stages of the process and diffusion. The state of the medium depends on concentrations of initial reagents used in BZ reaction and temperature. Small changes of concentrations ~ 0.05 M and temperature ~ 0.1° do not have significant influence on the type of dynamic process. At the same time these media are available, stable, non-hostile reagents. Furthermore the temperature range and temporal operation scale of the


8

RAMBIDI, et al.

medium dynamics are convenient for investigation with available physical methods. The BeIousov-Zhabotinsky type media based on a light-sensitive catalyst are the most convenient for investigation purposes and broaden significantly information processing capabilities of the medium. Resilience Intense illumination in visible spectral region (white) is an inhibitory factor that turns the medium into initial uniform state and annihilates traces of previous experiments. Diversity The important point for understanding the essence of the reactiondif fusion paradigm is neural network architecture of the chemical reaction-diffusion information processing media. Let us outline a number of features that would determine their information processing characteristics. Let us reduce also this consideration to the case of pseudo-planar networks with lateral connections that seem to correspond to thin layers of reaction-dif fusion media. Dif ferent approaches to describe these networks are known, starting with the pioneer work by McCulloch and Pitts [17]. Beginning from the late sixties, Grossberg launched a detailed investigation of these networks (see [27]) based on psychobiological and neurobiological data. Grossberg concluded that shunting on-center off-surround feedback networks display a number of remarkable features. These neural n0etworks display the short-time memory. They proved to be also capable of quenching noise (sharpening) or amplifying noise (broadening) of input signals, or of enhancing a signal's contour of the most intense fragments of the signal. Grossberg [28] has noted a dynamic analogy between shunting on-center of fsurround feedback neural nets and reaction-diffusion systems, which were used by Gierer and Meinhardt [29] for the description of the process of biological pattern formation. The dynamics of Belousov-Zhabotinsky system is determined by kinetics of chemical reactions proceeding in the system and diffusion of reaction components. The kinetics should include a positive feedback (such as autocatalysis) on a species called activator and an inhibitory process. Moreover, the inhibitor should diffuse much faster than the activator (see details in [30]). These chemical mechanisms are the bases of the dynamic similarity between on-center off-surround neural nets and BelousovZhabotinsky media.


REACTION-DIFFUSION PARADIGM

9

FIGURE 1 Neural network architecture of reaction- diffusion medium.

The similarity of information processing capabilities of these two objects was successfully confirmed by experimental modeling of two examples considered by Grossberg and Todorovich [31], namely evolution of the Hermann grid and the two-dimensional analogue od an unevenly illuminated one-dimensional scene, based on Belousov-Zhabotinsky media [32]. Specific features of Belousov-Zhabotinsky neural net architecture should be mentioned. Cells (Fig.1) small by comparison with the diffusion length can be considered as primitive processors representing chemical systems having point wise kinetics. If these cells are to be considered as independent, trigger and oscillatory regimes should be inherent. Diffusion length (the distance, where total intermixing of reaction components has taken place) is determined as 1D=(DT)1/2. Here D is an average diffusion coefficient and T is a characteristic time of the dynamic process. Individual cells are coupled into a system having lateral connections because of diffusion. This coupling determines a number of complicated dynamic modes that are displayed in thin layers and in a volume of the medium. Changing the composition and temperature of the medium can provide control of the medium regimes. Generally speaking, each cell is connected to each other cell of the medium due to diffusion coupling. This interaction is carried out with a time


10

RAMBIDI, et al.

delay proportional to the distance between cells and the strength of the interaction decreases proportionally to this distance. Given the dynamical similarity between Belousov-Zhabotinsky media and on-center off-surround Grossberg networks it is reasonable to conclude that a lot of problems solved by Grossberg networks could be also solved by devices based on chemical reaction-diffusion media. Between them should be problems of high computational complexity such, as image processing and recognition, and other similar tasks.

INFORMATION PROCESSING CAPABILITIES OF BELOUSOV-ZHABOTINSKY MEDIA Experimental implementation of reaction-diffusion information processing technologies. Several slightly different versions of using reaction-diffusion media to perform information processing operations were described in literature see, for instance, [4,6,8,9,24]). Let us consider as an example operational features of the polymer based reaction-diffusion processor that have been used in our lab [24]. The heart of this processor is thin (0.5-1.5 mm) layer of silica hydro gel were the catalyst of BelousovZhabotinsky reaction is immobilized. ll other chemical components of the reaction are in the solution saturating polymer layer. Such design of the processor enables to avoid distortions of chemical component distribution in the layer because of mechanical pushes and vibrations, hydrodynamic processes and so on. There are several operational modes of the processor (Fig.2): (i) Uniform visible light radiation of highintensity removes traces of previous experiments and bring the processor to its initial state. (ii) Non-uniform spatial distribution of chemical components arises in the medium due to chemical reactions initiated by the photosensitive catalyst due to non-uniform light illumination. Therefore the catalyst works as a "macro-micro" interface that gives the opportunity to input initial information in the medium. (iii) The process of evolution of initial concentration distribution proceeds in the media due to chemical reactions and diffusion. The catalyst changes its electronic state in the course of reaction when the medium goes from one stable state into another. As a consequence, the reagent changes its color (from red to blue and vice versa) and it is easy to visualize the process and


REACTION-DIFFUSION PARADIGM

11

FIGURE 2 Operational modes of the experimental set up for the investigation of reaction-diffusion media information processing capabilities: removing traces of previous experiments (A), input of initial information (B), record of temporal evolution of the input data (C), control of the process of the image evolution (D)

to observe its spatio-temporal evolution. Therefore the catalyst works also as a "micro-macro" interface bringing into correspondence optical (macro) image of the process and evolution of the chemical concentration distribution. In practice the illumination of the medium is necessary to record its evolution. The intensity of the illumination should be chosen carefully: to be sufficient to record temporal evolution of the input picture by video camera, and to be insufficient to change the dynamic mode of the light-sensitive medium used. (iv) It is important that light radiation could be used also for the control of the medium evolution. The dynamic mode of the initial process doesn't change in the fields of the medium that are not illuminated during the process evolution. At the same time the initial process is killed in the fields where the medium is illuminated by the white light. It enables, for instance, to create obstacles of predetermined shape for concentration pulses spreading in the medium and so on. Technical characteristics of the set up used were the follows. The specific feature of the set up was computer controlled Sanyo PLC-510M LCD video projector (VGA compatible, 270 ANSI lumens). High uniformity of the background intensity of this projector improved the reliability of the experiment. At the same time the computer-controlled projector was indispensable for the control of the image evolution performed by the


12

RAMBIDI, et al.

FIGURE 3 Processing black and white (positive ­ 1, and negative ­ 2) and half-tone (positive ­ 3, and negative ­ 4) images by a chemical reaction-diffusion medium.

medium. Light-sensitive catalyst Ru(bpy) 3Cl 2 was immobilized in the thin layers of silica hydro gel or on the surface of the solid support placed at the bottom of the reaction vessel. The SILUFOL UV254 plates for thin layer liquid chromatography (0.25 mm layer of silica gel placed on the aluminum foil support) were used. Mintron OS-045D video camera was used to record steps of image processing by the medium (0.02 lux sensitivity, 600 TV lines resolution). Image processing Evolution of black and white picture is determined by the state of the medium, by exposure of the medium illumination, and by the positive or negative character of the input picture. The evolution of halftone picture is more complicated and depends additionally on the optical contrast of the input picture. Examples of these processes are shown in Fig.3. It was found during the last decade that chemical reaction-diffusion media can be used effectively for information processing.


REACTION-DIFFUSION PARADIGM

13

FIGURE 4 Responses of reaction-diffusion media to the input of black and white images: smoothing of immaterial features (1), removing of small details (2), defect repair (3).

Black and white image processing operations performed by reactiondif fusion chemical media proved to be similar to the human visual capabilities and dependent on the state of the medium (see [24] and references to it). There are two dif ferent fields of image processing capabilities inherent in chemical reaction-diffusion media (Figs.4,5). The first of them can be defined as "description of the general features of an object". This set includes such primitive operations as concentration on the general outline of an image (Fig.4.1), removing small immaterial features (Fig.4.2), "addition to the whole" operations, and, in particular, restoration of an image having defects (Fig.4.3). The second field can be determined as "switching to the details of an image". It includes contour enhancement (Fig.5.1), segmentation, that is division of an image into simple parts (Fig.5.2), image skeletonizing, enhancing small features of an image (Fig.5.3). The process of image evolution, if the image is a combination of fragments having different brightness, begins in the medium with a delay depending on the brightness of corresponding fragment. Therefore fragments reveal in the course of evolution in consecutive order beginning from the less bright ones. The light-sensitive reaction-diffusion medium transforms the spatial distribution


14

RAMBIDI, et al.

FIGURE 5 Responses of reaction-diffusion media to the input of black and white images: contour enhancement (1), segmentation (2), enhancement of small features (3).

of fragments having different brightness in a temporal consequence of revealing fragments. An image similar to pictures taken from satellites or reconnaissance planes was designed. Results of its processing by BelousovZhabotinsky type medium are shown in Fig.6. It could be seen that the darkest fragments are enhanced first in the process of evolution and after that the most light ones. Therefore the use of these media seems to be attractive potential way for the processing of satellite or aerial information. Finding the shortest paths in a labyrinth The phenomenon of consecutive enhancement of fragments having different brightness was used as the basis for elaboration of technique for finding the shortest paths in a labyrinth [24]. The basic feature of the procedure is that the labyrinth should be stored in the memory as an image (in the simplest case, as a black and white image, for instance, black picture of the labyrinth on the white background). Let a starting point of a labyrinth be defined and a procedure be designed that would give the opportunity to record consecutive steps of the wave spreading to the computer memory. When the wave spreads along the path in the labyrinth, the black color


REACTION-DIFFUSION PARADIGM

15

FIGURE 6 Artificial aerial picture (1) and its evolution in a reaction-diffusion medium (2).

of the labyrinth path changes to the color of the background. The spreading of the wave through a labyrinth is a parallel operation of high computational complexity. A reaction-dif fusion medium is able to perform effectively this operation, and consecutive steps of it could be stored in a memory of digital computing system and could be processed by digital computer (Fig.7). Let a controlled non-uniform background of some predetermined shape be superimposed on an initial labyrinth image. And this combined picture is used instead of the initial image. Then a light-induced phase wave controlled by the shape of the background will spread through the paths of the labyrinth changing the color of it from black to white. This process could be recorded by video system and its successive realizations are initial data for finding paths in the labyrinth. The wave spreading in the labyrinth beginning from the starting point of the labyrinth to its target points is shown in Fig.7. Since this process is taking place for about 3 - 5 seconds it is easy to record consecutive steps of this spreading by a video camera and store these records in the


16

RAMBIDI, et al.

FIGURE 7 Finding the shortest paths in a tree-type labyrinth:L1-L4 are consecutive steps of the labyrinth evolution in the process of wave spreading, L1-1 is the step L1 after spreading the wave from the labyrinth output, L1-2 is the result of subtracting non-connected with output fragment from L1 image, LF is the shortest path in the labyrinth.

computer memory. Some of these records are shown in Fig.7. In the process of the wave spreading when the wave passes over a branching point the labyrinth is divided into two (or more) fragments. One of these is connected with the output, but the other one is not. It is easy to find the fragment connected with a target point of the labyrinth if a backward wave is initiated in the medium at this point. As a result fragments connected with a target point change their color (from black to the color of labyrinth background) while the color of the non connected fragment remains unchanged. Successive repetition of this procedure at every branching point gives the opportunity to exclude all blind channels (and paths to other possible target points) and to determine the path from the starting to the target point. Detailed description of the procedure is discussed in [13].


REACTION-DIFFUSION PARADIGM

17

WHAT'S NEXT? There are three mutually correlated hypostasis's of reaction-diffusion paradigm that define the understanding of its potentialities. They are: - theoretical reasons, - operational opportunities to implement them, - the most important fields of application Theoretical reasons Unlike the digital von Neumann computer, the reaction-diffusion device is not a rigid structurally predetermined system. Its dynamics depends on the composition and control stimuli variations. It enables implementation of rather effective control of the dynamics. Even simple reaction-diffusion systems display high degree of parallelism, discrete and continuous dynamic mixed, and vertical flow of transmission and processing information. Even in a simple system the following can be determined: - the level of macro-micro type transformation of information (particularly, photochemical transformation of a light two-dimensional picture into pseudo two-dimensional distribution of reaction components), - dynamics at the molecular level implementing a definite information process, - the level of micro-macro information transformation, i.e. physicochemical reading information. High degree of organization is inherent in molecular media of this type. Moreover, these media display gradualism, i.e. small changes of active medium composition, within define limits, lead only to small quantitative, not qualitative changes of system dynamics. It is essential that media of Belousov-Zhzabotinsky type have also other characteristics necessary for displaying adaptive behavior. Among these is the nature of interaction of the system with the environment, feedback organization, etc. Therefore it is possible to conclude that it could really be possible to create a device, capable of learning, having multilevel architecture and a high degree of behavioral complexity. In general the detailed comparison of the information features of the brain, the digital von Neumann computer and reaction-diffusion media leads to the conclusion that there is a suf ficiently greater analogy between features of reaction-diffusion media and the brain, which is the system that solves problems of high computational complexity in a natural way.


18

RAMBIDI, et al.

Potentialities for the commercial use Regretfully, experimental technique used now for material implementation of these theoretical reasons is in a primitive embryonic state. Therefore the laboratory-scale devices discussed above looks nowadays as beautiful toys, not as a basis for commercial devices. However the thorough analysis shows that reaction-diffusion media seem to be promising even now for fabrication of new effective information processing means. Let us return to the example discussed above - contour enhancement by reaction-dif fusion medium. The time of this primitive operation performed by the medium is about 1-5 sec. It was shown above that the number of floating-point operations necessary to solve this problem by digital computer is about 5?106 if the resolution of the picture is 103?103. Average time of floating point operation (multiplication) performed by Pentium III processor (600 Mhz) is about 3?10 -9 sec. And the time of contour enhancement is ~ 10-2 sec. However this time increases greatly if the resolution of the picture should be 104?104 - ~ 1 sec, or 105?105 - 100 sec. The computational complexity of the object in this example is not high. Nevertheless the computational performances of reaction-diffusion medium and digital computer could be comparable. Given a problem of high computational complexity the performance of the reaction-diffusion medium could be sufficiently increased even by orders-of-magnitude. The very important advantages of reaction-diffusion means should be simplicity and low commercial mass production costs. The material structure of reaction-diffusion devices is immeasurable simpler than VLSI. Therefore the technological basis for the fabrication of reaction-diffusion devices should be simpler and cheaper. The reaction-diffusion media are impurity tolerant in comparison with semiconductor devices. It leads to additional opportunities to decrease processing capabilities and cost. Fields of application The progress of the human society faces more and more new challenges - simple, cheap, autonomous, massively deployed means capable to collect and store information, and to solve intellectual problems such as recognition, control and navigation. These systems should sense external stimuli and respond in real or near -real time. Important challenges embrace, for instance, the ocean self exploration, the nano satellite system deployment, military and dual-use applications such as mobile robots that work in dynamically changing environments.


REACTION-DIFFUSION PARADIGM

19

The real time for these systems is often ~ 0.1 - 1.0 sec. Moreover, the shelflife of such means could be rather short. Chemical and biochemical reaction-diffusion media seem to be an attractive basis for fabrication of these devices. They are capable of natural style performing of intellectual operations. Mention that information processing capabilities and problems that could be efficiently solved based on reaction-dif fusion systems seem to be far from exhausted. A number of approaches could result in advanced powerful information processing means. Several possibilities could be mentioned which might be important for the future development reaction-diffusion information processing means. Promising theoretical and experimental investigations were performed during the last several years (see details in [24]) though most of them was not bound directly to information processing. However it should be reasonable to suppose that because of biological nature of the reaction-diffusion paradigm the biologically inspired principles would be indispensable to greatly broaden information processing capabilities. The most important between them seems to be the multi level or ganization of biological information processing. The understanding of the importance of multi level architecture was growing during the last years [24]. And it is necessary to take the next step - to realize, to choose, and to put together: - practical problems most adequate to non von Neumann computing, - to find multi level algorithms for solving these problems, - to elaborate experimental technique to implement these algorithms. Let us hope that it would be done in the nearest future. If successful, these efforts will create fundamentally new devices that rather supplement than compete with modern digital semiconductor computers broadening immensely the power of "information industry".

REFERENCES
[1] H. Abelson, D. Allen, D. Coore, Ch. Hanson, G. Homsy, T.F. Knight, Jr., R. Nagpal, E. Rauch, G.J. Sussman, R. Weiss, Amorphous computing, Comm. of the ACM 43, ?5, 7582, 2001. [2] S. Wallach, Update on High-End Computing Research and Development, http://www.hpcc.gov/pitac/ pitac-10may01/wallach.pdf. [3] L. Kuhnert, A new optical photochemical device in a light-sensitive chemical active medium, Nature 319, 393-394, 1986. [4] L. Kuhnert, K.I. Agladze, V.I. Krinsky, Image processing using light-sensitive chemical waves, Nature 337, 244-247, 1989.


20

RAMBIDI, et al.

[5] O. Steinbock, P. Kettunen, K. Showalter, Chemical wave logic gates, J. Phys. Chem. 100, 18970-18975, 1996. [6] O. Steinbock, A. Toth, K. Showalter, Navigation complex labyrinth: optimal paths from chemical waves, Science 267, 868-871, 1995. [7] T. Sakurai, E. Mihaliuk, F. Chirila, K. Showalter, Design and control patterns of wave propagation in excitable media, Science 296, 2009-2012, 2002. [8] D. Tolmachev, A. Adamatzky, Chemical processor for computation of Voronoi diagram, Adv. Mater. Optics Electron. 6, 191-196, 1996. [9] A. Adamatzky, D.Tolmachev, Chemical processor for computation of skeleton of planar shape, Adv. Mater. Optics Electron. 7, 135-139, 1997. [10] N.G.Rambidi, V.M.Zamalin, Yu.M.Sandler, Molecular information processing devices and artificial intelligence problem, J.Mol.Electron. 4, 839-848, 1988. [11] N.G.Rambidi, An approach to computational complexity, Nondiscrete biomolecular computing, Computer 25, 51-54, 1992. [12] N.G.Rambidi, Biomolecular nonlinear dynamic mechanisms as a foundation for human traits of information processing machine, Discrete Dynamics in Nature and Society.6, 263-279, 2001. [13] N.G.Rambidi, D.Yakovenchuk, Chemical reaction-diffusion implementation of finding the shortest paths in a labyrinth, Phys. Rev. E 63, 026607, 2001. [14] N.Rambidi, Roots and promises of chemical-based computing, BioSystems 64,169-178, 2002. [15] N.G.Rambidi, K.E.Shamayaev, G.Yu.Peshkov, Information processing using lightsensitive chemical waves, Phys. Lett. A 298, 375-382, 2002. [16] N.G. Rambidi, Lure of molecular electronics ­ from molecular switches to distributed molecular information processing media, Microelectronic engineering 69, 485-500, 2003. [17] W.J. McCulloch, W. Pitts, A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics 5, 115-133, 1943. [18] F. Rosenblatt, Principles of neurodynamics. Perseptrons and the theory of brain mechanisms (Spartan Books, Washington, D.C., 1962). [19] A.T. Winfree, Electrical turbulence in three-dimensional heart muscle, Science 266, 10031006, 1994. [20] P.C. Newell, Aggregation and Cell Surface Receptors. In: J.L.Reissig, (ed.): Cellular Slime Molds in Microbal Interaction. Receptors and Recognition, Series B (Chapman and Hall, 1977). [21] D.E. Woodward, R.Tyson, M.R. Myerscough, J.D. Murry, E.O. Budrene, and H.C.Berg, Spatio-temporal patterns generated by Salmonella Typhimurium, Biophys. J. 68, 21812189, 1995. [22] A. Goldbetter, Biochemical Oscillations and Cellular Rhythms (Cambridge University Press, Cambridge, 1997). [23] A.S. Davydov, Solitons in molecular systems (Naukova Dumka, Kiev, 1984, in Russian). [24] N.G. Rambidi, Chemical based computing and problems of high computational complexity: reaction-diffusion paradigm. In: T. Sienko et al (eds): Molecular Computing (MIT-Press, 2003). [25] K.P. Zauner, M. Conrad, Parallel computing with DNA: toward the anti-universal machine. In: 4th International Conference on Parallel Problem Solving from Nature, (Berlin, Germany, 1996). [26] R.J. Field, M.Burger, eds., Oscillations and traveling waves in chemical systems, (WileyInterscience, New York, 1985).


REACTION-DIFFUSION PARADIGM

21

[27] S. Grossberg, Nonlinear neural networks: principles, mechanisms, and architectures, Neural Networks 1, 17-61, 1968. [28] S. Grossber g, On the development of feature detectors in the visual cortex with applications to learning qnd reaction-diffusion systems, Biological Cybernetics 21, 145159, 1976. [29] A. Gierer, H. Meinhardt, A theory of biological pattern formation, Kybernetik 12, 30-39, 1972. [30] V. Castets, E. Dulos, J. Boissonade, P. De Kepper, Experimental evidence of a sustained Turing-type nonequilibrium chemical patterns, Phys. Rev. Lett. 64, 2953-2956,1990. [31] S. Grossberg, D. Todorovic. In Neural Networks and Natural Intelligence, S. Grossberg (ed.), MIT Press, Cambridge, MA, 1989. [32] N.G. Rambidi, A.V. Maximychev, Molecular image processing devices based on chemical reaction systems. 6: Processing half-tone images and neural network architecture of excitable media, Adv. Mater. Optics Electron, 7, 171-182, 1997.