3.10 Dynamical Circuits: Collision-Based Computing

3.10 Dynamical Circuits: Collision-Based Computing

In dynamical circuits, autonomous signals travel in a uniform space. Truth values are represented by either the presence or absence of information quanta or by various states of the traveling pattern, and perform computation by colliding with other traveling signals. The traveling is analogous to information transfer, while collision is an act of computation—thus we call the setup collision-based computing. There are three sources of collision-based computing: a proof of universality of Conway's Game of Life via collisions of glider streams (Berlekamp, Conway, and Guy 1982); a conservative logic and its implementation in a billiard ball model (Fredkin and Toffoli 1982); and a concept of computation in cellular automata with soliton-like patterns—the particle machines (Steiglitz, Kamal, and Watson 1988; classical papers and recent advances can be found in Adamatzky 2002).

In a series of papers (see, e.g., Adamatzky 1998, 2000, 2001), it was proved that twoand three-dimensional cellular automata models of excitable media are minimal computationally universal machines. The model and accompanying results are too technical to talk about in the present chapter. Suffice it to say that logical gates in discrete excitable lattices can be implemented via the collision of two or more particle-like waves—compact mobile patterns of excitation with particle-like behavior. These waves are similar to nonlinear self-localized excitations found in physical systems (e.g., breathers and solitons). Because this book is preferentially about wet-ware rather than abstract constructs, we will provide mainly computational examples of "natural" systems that can do collision-based computing. We will discuss breathers in DNA molecules, mobile excitations in molecular arrays, and quasiparticles in gasdischarge systems.

Forinash and others (Forinash, Peyrard, and Malomed 1994; Forinash, Cretegny, and Peyrard 1997) studied a Hamiltonian with two variables, which describes the transverse displacement of a DNA molecule under different values of the coupling between nucleotides along the same strand. They observed the spontaneous formation of intrinsic local modes, which, as the authors predicted, emerge because of localization of thermal fluctuations and grow due to the exchange of energy. In computational experiments, using a numerical solution of the equation of motion, Forinash and Colleagues demonstrated that a typical self-localization—a breather—is mobile: Being excited, the breather travels along DNA strands. The breathers interact with each other and with defects, natural or artificial, in the DNA molecule (Forinash, Cretegny, and Peyrard 1997).

What types of breather-collision-based gates can be implemented in a DNA molecule? We display a modest catalog of DNA breather gates in figure 3.7. The gate 1G-A is quite a common gate in the family of collision-based gates: When two breathers collide, they undergo phase shifts and thus arrive to checkpoints earlier or later than noncolliding breathers. In some cases, a third localization is formed in the collision of two breathers. Usually it remains immobile; this stationary localization depicts a logical conjunction of two variables represented by the colliding breathers (figure 3.7, 1G-B). The gate 1G-C is an amalgam of the two previous gates: Colliding breathers are delayed or sped up and the third stationary localization is formed.

Figure 3.7: Catalog of spatio-temporal gates implemented in a model of a DNA molecule in the collisions between two breathers (1G-A, 1G-B, 1G-C) or between one (1G-D, 1G-E, 1G-F, 1G-G) or two (1G-G) breathers and an impurity. Time goes downward. Positions of nucleotides are indexed rightward.

The next four gates (1G-D, 1G-E, 1G-F, and 1G-G) are derived from the interaction of a breather with an impurity (Forinash, Peyrard, and Malomed 1994) in a model of a chain of harmonically coupled particles influenced by asymmetric on-site potentials. Both resting and excited impurities are considered. When a breather collides with a resting impurity, four possible outcomes of the collision are expected, depending on the breather's amplitude and the mass of the impurity: (1) the breather passes through the impurity without any sufficient changes in the breather's form and energy, (2) the breather is trapped by the impurity and it stays at the impurity site (1G-D), (3) one part of the breather excitation becomes trapped by the impurity mode, the other part is reflected (splitting or partial reflection of the breather by impurity: 1G-E), and (4) the breather is reflected by the impurity.

The second scenario above—the "breather-impurity" collision—gives us the construction of the gate 1G-D. Assume a resting impurity is not detected, thus when a breather collides with the impurity and becomes trapped, a conjunction of two Boolean variables represented by the breather and the impurity is calculated. The gate 1G-E is devised from the third and the fourth scenarios of the collision. In some cases, it is also possible to slow down a breather by an impurity: The breather may be trapped at the impurity site for a long time until it escapes later with a reduced velocity (Forinash, Peyrard, and Malomed 1994; figure 3.7, 1G-F).

What happens when a breather collides with an excited impurity? Results of the collision depend on the relative phases of the breather and the impurity (Forinash, Peyrard, and Malomed 1994): The breather is trapped by the impurity if the distance between the initial position of the breather and impurity sites is odd; the breather passes through the impurity otherwise. Let two breathers head for a resting impurity. We can adjust their distances such that the following scenario occurs: The first breather passes through the impurity and leaves the impurity in an excited state. The second breather therefore collides not with the resting impurity but with the excited one. Depending on the distance between these two breathers, the second breather may be captured by the impurity or pass along it (Forinash, Peyrard, and Malomed 1994). Thus we obtain the structure of the gate 1G-G. For a certain set of parameters, it is possible to implement a fusion of two breathers via collisions with a resting impurity: The breathers are fused in a single (im)mobile breather (Forinash, Peyrard, and Malomed 1994). When two breathers pass through a resting impurity, the first breather may be trapped. When a second breather arrives at the impurity site, it is also trapped. The trapping is reversible because both captured breathers give rise to a larger breather that can start its own motion. This means a resting impurity can play the role of a summator—we set up the parameters in such a fashion that only the energy of n breathers, trapped by the impurity, is enough to start a large mobile breather. The impurity may be considered an elementary threshold summator, which takes the value 1 if it accumulates at least n breathers, and the value 0 otherwise.

Our speculations about possible designs of one-dimensional breather machines fit well in a framework of computation in one-dimensional cellular automata, where interaction of traveling signals is the main issue (see, e.g., Mazoyer 1999; Delorme and Mazoyer 2002). We also briefly mention that the automaton representation of localized excitations and its application to computing in regular structures and bulk media received much attention in the academic community after the advent of the Park-Steiglitz-Thurston model of soliton-like mobile patterns in one-dimensional cellular automata (Park, Steiglitz, and Thurston 1986; Steiglitz, Kamal, and Watson 1988; Jakubowski, Steiglitz, and Squier 2002).

Two-dimensional computers exploiting the principles of collision-based computing can be fabricated from molecular aggregates capable of directed transfer of energy. What happens when we optically excite an electronic system in light-sensitive molecular aggregates? Two competitive mechanisms are activated: localization and delocalization (Toyozawa 1983). The first mechanism is based in the imbalance of forces activated by electronic charge redistribution and acts on relevant atoms to find new equilibria of molecular configuration coordinates; this destroys resonance of electronic excitation to the neighboring sites. The second mechanism relies on molecular resonance; it is responsible for the transfer of excitation from one site of the molecular aggregate to another site. The localization of excitation emerges due to interplay between the localization and delocalization. Scheibe aggregates are the most suitable candidates for the role of a molecular-array computer.

To make a Scheibe aggregate, we mix oxacyanine dye molecules with inert molecules to form a monomolecular array. Then we add thiacyanine dye molecules: Donor molecules of the oxacyanine group are replaced by acceptor molecules of the thiacyanine group (B cher and Kuhn 1970; Moebius and Kuhn 1979; Bartnik and Tuszynski 1993); the fabricated array can then be transferred to a solid substrate. If the array contains at least one acceptor molecule to 10⁴ donor molecules, it absorbs energy of photons and transfers this energy over long distances without losses sufficient for degradation (Moebius and Kuhn 1979; Bartnik and Tuszynski 1993). When a photon is absorbed into the aggregate, a domain of excitation is generated: The domain occupies eight molecules nearest to the acceptor molecule, which oscillate in phase at the frequency of fluorescence. The domain moves across the monomolecular array (Bartnik, Blinowska, and Tuszynski 1991, 1992) with supersonic speed; the domain's size (about 27 27 ) is conserved. This domain is called an exciton (Nolte 1975; Moebius and Kuhn 1979).

The moving excitons may undergo mutual annihilation when within each other's influence (Kenkre 1983), thus a gate NOT(y) AND x can be implemented in exciton collisions (figure 3.8a). Actually, we can find two-dimensional analogies of almost all DNA breather gates; the time-space separation of input and output trajectories in DNA breather gates is substituted here by space-space separation of exciton trajectories in molecular arrays. Let us mention a few exemplar collisions:

Figure 3.8: Exemplar gates realized in collision of two-dimensional self-localized excitations.

The colliding of two localizations can produce the third stationary localization: This stationary localization represents a conjunction of the signals represented by two colliding localizations (figure 3.8b). The stationary localization can be detected via a collision with another mobile localization. For a particular set of parameters, two colliding localizations form an unstable bound state and split again, hence angles of their velocity vectors are changed. This gives us quite a peculiar topology of the and gate (figure 3.8c).

Conditions may also be satisfied when a third mobile (daughter) localization is formed in the binary collision of localizations. This new localization may be diverted to other routes and thus multiplication of a signal is implemented.

To realize the logical truth constant, we need a continuous stream of mobile localizations. Such a stream could be generated by some kind of a particle-gun, which periodically produces the coherent mobile patterns. Several types of guns of self-localized excitations in two and three dimensions are studied in Adamatzky (1998, 2001). Despite their sound theoretical background and great variety of forms, the experimental verification of such guns only recently was confirmed. Namely, in numerical experiments based on solutions to the discrete nonintegrable thermalized Schr dinger equation, Rasmussen and Colleagues (1999) demonstrate that discrete breathers cause large phonon fluctuations in their neighborhood. The fluctuations increase a probability of new breather generation in the vicinity of the old one. This newly born breather may be ejected as a propagating breather; meantime, the stationary "old" breather recovers after the generation of the mobile "daughter" breather and repeats the "labor".

Recently, we were studying universal computation in simulated and laboratory prototypes of active chemical media or in their discrete analogues (i.e., excitable lattices; Adamatzky 1998, 2000, 2002). As a result, our collision-based computing model of universal reaction-diffusion computers lacked an experimental proof. Luckily, the situation changed because of experimental findings obtained in Professor Purwins's laboratory (University of M nster), using an experimental setup based on a gas discharge system (a mixture of argon with air between two planar electrodes, a highly resistive semiconductor anode, and a metallic cathode). It was shown that with increasing voltage supply, a number of current density filaments or quasiparticles are formed (Bode and Purwins 1995). The filaments may travel in the system and collide with each other. Experimentally observed collisions include quasielastic collision, annihilation, formation of bound state of two quasiparticles, and generations of the third quasiparticle (due to interaction of the quasiparticles' oscillating tails) (Astrov and Purwins 2001)—that is, the full spectrum of collisions sufficient to implement a functionally complete system of logical functions. In terms of a two-component reaction-diffusion system, a current density distribution or a concentration of charge carriers in the gap between electrodes is analogous to an activator, and an increase in voltage drop, diffusing from domains with over-threshold current, is an inhibitor.

The findings were confirmed in numerical simulations of the three-dimensional system, where for certain combinations of reaction rates and diffusion speeds of inhibitor and activator, one can produce the development of quasiparticles (Schenk et al. 1999; Liehr, Bode, and Purwins 2001). The structure of the quasiparticle—with an activator-head and an inhibitor-tail—gives an excellent continuous-space analogue of our early discrete models of particle-like waves in three-dimensional lattices (Adamatzky 1998, 2001).