Computing in Nonlinear Media and Automata Collectives

Citation

(2001), "Computing in Nonlinear Media and Automata Collectives", Kybernetes, Vol. 30 No. 9/10. https://doi.org/10.1108/k.2001.06730iae.001

Computing in Nonlinear Media and Automata Collectives

Andrew AdamatzkyInstitute of Physics PublishingBristol and Philadelphia, PA2001395 pp.ISBN 075030751X. ISBN 075030751X.£80/$130 (hardback) £80/$130 (hardback)

Keywords: Publication, Cybernetics, Computing

This book aims to show how to design parallel processors from masses of simple locally interacting uniform substances. Computing in excitable lattices, processing in chemical thin liquid layers and construction from amorphous swarms of social insects form the core subject of this volume which guides the reader from mathematical models of reaction-diffusion and excitable media to automata implementation of massively parallel processors to fabrication of real-life computing devices. Numerous amusing examples aim to entertain those already bored with dry theories or grounded applications.

The spreading and interaction of substances are the main tools of reaction-diffusion computing. Various types of propagation fronts are the essential attributes of all natural systems from heat transfer to population dynamics to neural activity. Most of these phenomena can be adequately described in terms of reaction diffusion systems, where reactants are converted into products during the propagation of a wavefront.

Most imagined, simulated and real-life chemical processors obey a very simple scheme of action. A medium is at rest at the beginning of a computation. Data are transformed into the spatial configuration of a geometrical object. This configuration is cast onto the medium. After projection, the elements of the data configuration form an ornament of local disturbances in the medium% characteristics, e.g. drops of a reagent or an excitation pattern. The local disturbances generate waves. The waves spread in the medium. Eventually the waves, originating from different data sources, meet each other. They somehow interact and produce either a concentration profile of a precipitate or a stationary excitation structure. The emerging pattern represents the result of the computation. This scenario is exemplified in the second chapter.

From the first chapter we obtain a clue as to how a reaction-diffusion medium can compute. We are ready now to apply wave phenomenology to the solution of real problems. Reasonably we could start with a problem that has an underlying spatial structure and is open for intuitive solutions. We picked out three problems, which can be straightforwardly solved in a reaction-diffusion and excitable medium. So, the second chapter deals with the construction of Voronoi diagrams, skeletons and convex hulls. To construct a Voronoi diagram or a skeleton we employ distance-to-time transformations implemented as diffusive or phase waves spread. Thus, for example, in the Voronoi diagram of a planar set, waves are generated at given sites of data space, they spread out, interact with each other and form a stationary structure as a result of the interaction. This structure represents bisectors, separating the given site. Computation of a convex hull is also simple. Waves are generated at the given sites, spread out and merge into a single travelling pattern. Eventually the excitation pattern stops its growth at the boundaries of the requested convex hull. This chapter familiarizes readers with all the essential steps of reaction-diffusion processor design: from the mathematics of computation to cellular-automata models to laboratory prototypes of chemical processors. The text is spiced up with the computation of a Voronoi diagram in a swarm of mobile entities inhabiting a lattice and even more wild examples of the subdivision of the British Isles.

"From electricity to ant families through reaction-diffusion and excitation" could be a slogan for the third chapter. In contrast to the previous chapter, this part of the book deals with graphs. Here we consider the computation of various types of graphs, where selected sites of a space are connected, usually by graph edges, as well as computation on graphs, when graph edges and nodes update their states in parallel. The shortest-path problem is a good test for a new computing device, particularly unconventional ones. We show how to find the shortest path in cellular-automata models of excitable media and in real-life Belousov-Zhabotinsky reactors. In automata models and in laboratory prototypes of excitable chemical processors the shortest path is calculated from the wave velocity field, generated by waves propagating through computational space. Several types of proximity graphs are constructed in nonlinear media. Computation of a spanning tree is discussed in full detail. The mathematical background for the reaction-diffusion construction of spanning trees is based on three propositions: trees are approximated by random walks, random walks are similar to electrical flows and electrical flows are similar to diffusion. Various designs of analogue devices for shortest-path computation and spanning-tree construction are discussed thereafter.

Inspired by ideas of field computing we express some biological findings related to the motility-linked behaviour of amoeboids and the growth of neural terminals in an algorithm for the distributed construction of a minimum spanning tree. The algorithm is then transformed to computation of spanning trees in cellular-automata models of a reaction-diffusion medium. Reaction and diffusion at a macro-scale is exploited in our algorithms of swarm-based construction of spanning trees, where "diffusive ant families" play the role of an active nonlinear medium.

Chapters 2 and 3 give us examples of "specialized" processors. A processor is specialized if it is designed to solve some particular problem; for example, we could not use a reaction-diffusion processor that constructs the skeleton of a planar shape to do arithmetical calculations. Most real-life computers are universal. A device is called computation universal if it computes any logical function. Are reaction-diffusion and excitable media universal computers? The positive answer and proofs of media universality are given in the fourth chapter. There we give an overview of various types of computation universality, namely architecture-based and collision-based universality, and offer practical realization of universal processors in active nonlinear media.

Architecture-based computation assumes that a Boolean circuit is embedded into a system in such manner that all elements of the circuit are represented by the system's stationary states. This architecture is static. Three examples of architecture-based universality – sand-piles, mass transfer gates and wave gates – are discussed in detail. A dynamic, or collision-based, computation employs finite patterns, mobile self-localized excitations, travelling in space and executing computation when they collide with each other. The lion's part of the chapter is devoted to cellular-automata models of excitable media that exhibit a rich variety of mobile self-localizations. A remarkable spectrum of logic gates implemented in self-localization collisions is constructed. Most phenomena found in cellular-automata models are substantiated by real-life examples; i.e. we analyse the behaviour of solitons, light bullets, breathers, gaussons, excitons in monomolecular arrays and defects in tubulin microtubules in the context of collision-based computing.

While studying the construction of tesselations, proximity graphs and Boolean circuits in reaction-diffusion and excitable media we became proficient in the subject. We learn how to simulate nonlinear media, how to interpret a mathematical problem in terms of reaction and diffusion, how to design an algorithm and how to build a real-life chemical processor. We understand how problems with an underlying parallelism, like image-processing, graph theory and computation geometry, can be solved in cellular-automata models and natural media. Now we can assess, at least roughly, which problems can be solved in what types of nonlinear media. Should we fabricate these media from scratch or could we instead search for already existing specimens in nature? Chapter 5 offers an answer. We show which parameters of behaviour of medium's local elements can be taken into account when the computational properties of the medium are under scrutiny. Morphological, dynamical and computational classifications of excitable lattices are provided in this chapter together with several applications of emerging computation properties to image-processing and the control of robot navigation.

The book appeals to a wide auditorium: computer scientists, engineers, mathematicians, physicists, biologists and chemists.