Collision-Based Computing

Citation

(2003), "Collision-Based Computing", Kybernetes, Vol. 32 No. 3. https://doi.org/10.1108/k.2003.06732cae.008

Collision-Based Computing

Collision-Based Computing

Andrew Adamatzky (Editor)Springer-VerlagLondon2002 MayISBN 1-85233-540-8XXVII + 549 pp.paperback, 74,95

This book is about how to do computation in a structureless medium populated with mobile objects. No wires, no valves, nothing is there: just compact patterns wandering in space, smashing one to another and calculating. A computing device may be either generally purposive, universal, or specialised. A universal processor can do almost anything; specialised – almost nothing but one or two things. One may study two types of universality – logical, or computational, and simulational. An abstract machine as well as a real physical, chemical or biological system, is called computationally universal if it implements a functionally complete, or universal, set of Boolean functions in its spatio-temporal dynamic. All constructions studied in the book are computationally universal, because they realise universal systems of logical gates in collisions of mobile objects. If a system simulates behaviour of a universal machine, which universality has been already proved, it is called simulationally universal. Somewhere in this book you can find collision-based implementations of simulational universality, related usually to embedding of a Turing machine, a register machine, or a counter machine in a medium with colliding particles, balls or gliders.

A universal processing device can be either structured, heterogeneous, compartmentalised and stationary or structureless, homogeneous, architectureless and dynamic. Structured devices have wires to transmit information, valves to process it; structureless devices have nothing of it. Quanta of information are represented by mobile objects (either by their presence/absence of particular types, colors) that travel in the space. Trajectories of the objects can be seen as wires. The objects change their trajectories or states when smashed to other objects. Thus, information is transformed and computation is implemented. Present books deals with structureless computing devices.

The text starts with “Symbol Super Colliders” by Tommaso Toffoli, a chapter about physics and computation, importance of collision in physical and would-be worlds, and a “spacetime tapestry” of an artificial computation. The chapter is followed by three classical texts, showing how things were 20 years ago. They are “Design Principles for Achieving High-Performance Submicron Digital Technologies” (written in 1978 and never published before) and “Conservative Logic” (firstly published in 1982) by Edward Fredkin and Tommaso Toffoli; and, “Physics of Computation” (firstly published in 1984) by Norman Margolus.

The “modern time” of a collision-based computing theory is opened with “Universal Cellular Automata Based on the Collisions of Soft Spheres” chapter by Norman Margolus. Norman Margolus derives perfect momentum conserving models of ballistic computation by removing mirrors out of the computation space. He considers reflections without mirrors, crossover and routing of signals, dual-rail logic, and updates his original billiard ball model cellular automaton to incorporate soft spheres. Margolus's chapter closes with an intriguing excursion in relativistic cellular automata and semi-classical models of collision dynamics.

The study of ballistic computing models are continued in next two chapters. Thus in “Computing Inside the Billiard Ball Model” Jérome Durand-Lose applies his expertise in reversible computing, automata models of transition phenomena and grain sorting in sand piles to derive intriguing results related to reversible cellular automata models of collision-based computing. Firstly, Durand-Lose constructs block cellular automata, or partitioning cellular automata, as a generalisation of billiard ball model cellular automata. Then he shows, via implementation of reversible logic gates, that a two-counter machine is simulated in block cellular automata. Several problems of intrinsic universality and uncomputability in billiard ball model cellular automata are tackled in the chapter as well. Kenichi Morita with collaborators – “Universal Computing in Reversible and Number-Conserving Two-Dimensional Cellular Spaces” – show how to embed a Fredkin gate, which is a basic element of conservative logic, into a bitconserving reversible partitioning cellular automaton via generalisation of Margolus's billiard ball model cellular automaton to more complicated grids and advanced state transition functions.

Non-classical logical understanding of collision-based computing models are suggested in chapter “Derivation Schemes in Twin Open Set Logic” by Michael D. Westmoreland and Joan Krone. There you will find alternative derivation schemes and logical systems that may well describe ballistic models of computation in a more realistic way than it was done before. At this place of the book a reversibility of computation gives place to subjects of collision-based computing: gliders, particles, automata signals, solitons and other mobile 1ocalisations in non-linear media.

The chapter “Signals in Cellular Automata” by Marianne Delorme and Jacques Mazoyer presents a slice of modern theory of “geometrical computation” in one- and two-dimensional cellular automata. They study various types of cellular automata, which support propagation of information quanta, or signals. In particularly, they show how a cellular automaton can transform one type of a signal to another. They demonstrate how to design a one-dimensional cellular automaton that supports infinite families of signals of different speeds. Feasibility of Delorme-Mazoyer constructions is demonstrated in problems of multiplication in one-dimensional cellular automata.

Mariusz Jakubowski, Ken Steiglitz and Richard Squier in their chapter “Computing with Solitons: A Review and Prospectus”, makes a brief tour into a theory of particle machines and its application to computing with one-dimensional solitons. Various designs of soliton gates are discussed in a context of massively-parallel processors. This theme is continued by Pawel Siwak in “Iterons of automata”, where two classes of iterons, or iterating automaton networks, are considered. The first class includes mobile 1ocalisations, signals or particles, which emerge in classical cellular automata, cells of which update their states in parallel. The second class of iterons consists of travelling patterns arising in serially updated automata networks. The serial updating of an automaton chain is similar to a sort of filtering known as infinite impulse response or recursive filtering. Siwak's chapter gives us striking examples of phenomenology of particles in parallel and serial automaton chains.

Steve Blair and Kelvin Wagner – “Gated Logic with Optical Solitons” – look at collision-based computing from a practitioners point of view. They give an accessible introduction to digital logic and discuss a set of requirements to a logical gate. Blair and Wagner also show why solitons are good for collision-based computing; temporal, spatial and spatio-temporal soliton logic gates are designed there. Thus, to demonstrate that soliton logical gates may form self-consistent cascades with signal fan-out, Steve Blair and Kelvin Wagner study gate transfer function, details of spatial soliton dragging and collision interactions.

In his chapter “Finding Gliders in Cellular Automata” Andrew Wuensche describes how to classify cellular-automaton rules for a spectrum of ordered, complex supporting gliders, and chaotic dynamics. Also methods of “automatic” filtering of gliders and parametrisation of automata global dynamics are discussed there. The chapter arose from Andrew Wuensche's inquires into space-time dynamics of discrete matter at the edge of phenomenology and complexity.

There are travelling 1ocalisations everywhere – solitons in optical media, breathers in polymers, excitons in mono-molecular arrays, worms in liquid crystals, groups of oscillons in vibrating granular materials and quasi-particles in reaction-diffusion systems. The phenomena are discussed in Andrew Adamatzky's chapter “New Media for Collision-Based Computing”. An illuminating comparison of logical-gate architectures realised in “real” systems and their automata models gives us a vision of what types of collision-based computer prototypes can be built in laboratories.

Particle dynamics on two-dimensional lattices with fixed, rotating or flipping mirrors is amazingly interpreted in terms of Turing machines by Leonid Bunimovich and Milena Khlabystova in “Lorentz Lattice Gases and Many-Dimensional Turing Machines”. In their lattice gas model of a Turing machine, a particle, hopping from one vertex to another, represents a reading or writing head of the machine. The lattice is populated with mirrors, which are analogues of symbols, written on the tape; when travelling on the lattice, particles rotate or flip mirrors thus updating contents of the Turing tape.

The last three chapters of the book will entertain even those who are far from academic science. Self-replication and universal computing is the subject of the chapter “Arithmetic Operations with Self-Replicating Loops” written by Enrico Petraglio, Gianluca Tempesti and Jean-Marc Henry, who are experts in embryonic electronics, bio-inspired machines and evolving hardware. In their chapter, a cellular automaton is developed that is capable of self-replication, based on a modified version of the Langton loop. Namely, a paradigm of a particle machine (developed by Steiglitz, Jakubowski and Squier) is adopted in programming a self-replicating automaton, which implements basic arithmetical tasks such as binary addition and multiplication.

Game of Life cellular automaton is the first formal model which is proved to be collision-computationally universal. It is the most famous and the most talked about cellular automaton. Surprisingly, the Game of Life did not get proper treatment in academic journals – significant results and miraculous constructions are still attributed rather to cyberspace. The following two chapters of the volume will certainly attract more Game-of-Life fans to the field of collision-based computing. “Implementation of Logical Functions in the Game of Life” by Jean-Philippe Rennard gives a brief introduction to the subject of Game-of-Life-based computing and then shows particulars of logical gate implementation via collision of glider streams. Sophisticated and detailed constructions of Game of Life implementation of a universal Turing machine are presented by Paul Rendell in his chapter “Turing Universality of the Game of Life”. The constructions include an adder, a sliding block memory, a memory cell and many more fascinating parts. Even a finite state device and a Turing tape are designed from stationary cellular patterns, glider and spaceship guns, and other curiosities.

The book will be of interest to researchers working on relevant topics in computing science, mathematical physics and engineering. It will also be useful background reading for postgraduate courses such as optical computing, nature-inspired computing, artificial intelligence, smart engineering systems, complex and adaptive systems, parallel computation, applied mathematics and computational physics.

Further information can be found at: www.springer.de