Collision-Based Computing, Editor: A. Adamatzky (Springer-Verlag, 2002), XXVII, 556 pp. Softcover; 1-85233-540-8

Collision-Based Computing presents a unique overview of computation with mobile self-localized patterns in non-linear media, including computation in optical media, mathematical models of massively parallel computers, and molecular systems. It covers such diverse subjects as conservative computation in billiard ball models and its cellular-automaton analogues, implementation of computing devices in lattice gases, Conway's Game of Life and discrete excitable media, theory of particle machines, computation with solitons, logic of ballistic computing, phenomenology of computation, and self-replicating universal computers. Collision-Based Computing 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.

Molecular Computing, Editors: T. Sienko, A. Adamatzky, N. Rambidi, M. Conrad (The MIT Press, 2003), 280 pp. Hardcover; ISBN 0-262-19487-2

The next great change in computer science and information technology will come from mimicking the techniques by which biological organisms process information. To do this computer scientists must draw on expertise in subjects not usually associated with their field, including organic chemistry, molecular biology, bioengineering, and smart materials. This book provides an introduction to the interdisciplinary field of molecular computing. The book moves from abstract principles of molecular computing to the building of actual systems. The topics include the use of proteins and other molecules for information-processing, molecular recognition, computation in non-linear media, computers based on physical reaction-diffusion systems found in chemical media, DNA computing, bioelectronics and protein-based optical computing, and biosensors.



Table of contents (download PDF)

TOMMASO TOFFOLI: Symbol Super Colliders (Cellular Automata and Lattice Gases; Heat, Ice, and Waves; Colliding-Beams Particle Accelerators; Why Aristotle Didn't Discover Universal Gravitation; "On The Nature of the Universe")

EDWARD F. FREDKIN, TOMMASO TOFFOLI: Design Principles for Achieving High-Performance Submicron Digital Technologies Edward (Principles of Conservative Logic; Implementation of Conservative Logic in Concrete Computing Devices; Prospects for Applications to Sub-Micron Digital Technologies; Generalities; Josephson-Effect Switching; Integrated Optics)

EDWARD F. FREDKIN, TOMMASO TOFFOLI: Conservative Logic (Physical Principles Already Contained in the Axioms; Some Physical Principles that Haven't yet Found a Way into the Axioms; Conservative Logic: The Unit Wire and the Fredkin Gate; Fundamental Constraints of a Physical Nature; The Unit Wire; Conservative-Logic Gates; the Fredkin Gate; Conservative-Logic Circuits; Computation Universality of Conservative Logic; Nondissipative Computation; "Billiard Ball" Model of Computation; The Interaction Gate; Interconnection; Timing and Crossover, The Mirror; The Switch Gate and the Fredkin Gate; Garbageless Conservative-Logic Circuits; Inverse of a Conservative-Logic Network; Combinational Networks; Role of the Scratchpad Register. Trade-Off's Between Space, Time, and Available Primitives; Circuits that Convert Argument into Result; Energy Involved in a Computation)

NORMAN MARGOLUS: Physics-Like Models of Computation (Cellular Automata; Reversible Cellular Automata; Entropy in RCA; Conservation Laws in Second-Order RCA; First-Order RCA; The Billiard Ball Model; The BBM Cellular Automaton; Relationship of BBMCA to Conservative Logic; Energy in the BBMCA)

NORMAN MARGOLUS: Universal Cellular Automata Based on the Collisions of Soft Spheres (Fredkin's Billiard Ball Model; A Soft Sphere Model; Other Soft Sphere Models; Momentum Conserving Models; Reflections Without Mirrors; Signal Crossover; Spatially-Efficient Computation; Signal Routing; Dual-Rail Logic; A Fredkin Gate; Implementing the BBMCA; Signal Routing Revisited; Relativistic Cellular Automata; Semi-Classical Models of Dynamics)

JEROME DURAND-LOSE: Computing Inside the Billiard Ball Model (Block Cellular Automata; Reversibility; Relations with Classical Cellular Automata; Universality of One-Dimensional Block Cellular Automata; Billiard Ball Model; Basic Encoding; Conservative Logic; Dual Encoding; Reversible Logic; Turing Universality of the BBM Automaton; Counters; Intrinsic Universality of the BBM; Partitioned Cellular Automata; Intrinsic Universality of the BBM among R-CA; Space-time Simulation; Intrinsic Space-Time Universality of the BBM among CA; Uncomputable Properties)

KENICHI MORITA, YASUYUKI TOJIMA, KATSUNOBU IMAI, TSUYOSHI OGIRO: Universal Computing in Reversible and Number-Conserving Two-Dimensional Cellular Spaces (Number-Conserving Reversible Cellular Automaton; Embedding Fredkin Gate in Simple Universal Two-Dimensional Bit-Conserving Reversible Partitioning Cellular Automata; 16-State Model with Rotation and Reflection Symmetric Rules; 16-State Model with Rotation Symmetric Rules; 8-State Triangular Model; Compact Embedding of Reversible Counter Machine in Universal Number-Conserving Reversible Partitioning Cellular Automata)

MICHAEL D. WESTMORELAND, JOAN KRONE: Derivation Schemes in Twin Open Set Logic (Derived Logical Systems; Twin Open Set Logic; Twin Open Set Logic and Classical Logic; Derivation Schemes in Twin Open Set Logic; Nonstandard Derivation Methods; Derivation Schemes under Nonstandard Entailment; Nonstandard Implication; Tautologies in Twin Open Set Logics; Derivation Schemes in Collision Models)

MARIANNE DELORME, JACQUES MAZOYER: Signals on Cellular Automata (Signals and Grids; Transformations of Signals; Transforming Marks on a Cell into Some Right Signal; Some Right Signals from Some Other Ones; Infinite Families of Signals and Grids; Infinite Families of Signals; Computations and Grids; Infinite Families of Signals (or Waves) on Two-Dimensional Cellular Automaton)

MARIUSZ H. JAKUBOWSKI, KEN STEIGLITZ, RICHARD SQUIER: Computing with Solitons: A Review and Prospectus (Computation in Cellular Automata; Particle Machines, PMs; Simple Computation with PMs; VLSI Implementation; Particles in Other Automata; Solitons and Computation; Scalar Envelope Solitons; Integrable and Nonintegrable Systems; The Cubic Nonlinear Schrodinger Equation; Oblivious and Transactive Collisions; The Saturable Nonlinear Schrodinger Equation; Computation in the Manakov System; The Manakov System and its Solutions; Particle Design for Computation)

PAWEL SIWAK: Iterons of Automata (Homogeneous Nets of Automata; Cellular Automata; Parallel Processing of Strings; Linear Automaton Media; Serial Processing of Strings; Particles of Cellular Automata; Filtrons of Serial Processing; The Automata Based on FCA Window; Jiang Model; AKT Model; FPS Filters; F Model; FM Filters; BRS Models; Soliton Automata; Automata of Box-Ball Systems and Crystal Systems; Ball Moving Systems; Crystal Systems)

STEVE BLAIR, KELVIN WAGNER: Gated Logic with Optical Solitons (Solitons for Digital Logic; Temporal Soliton Logic Gates; Spatial Soliton Logic Gates; Spatio-Temporal Soliton Logic Gates; Cascadability of Spatial Soliton Logic Gates; Soliton Logic Gate Transfer Function; Interaction Details; Cascaded Inverters; Cascaded 2-NOR Gates)

ANDREW WUENSCHE: Finding Gliders in Cellular Automata (One-Dimensional Cellular Automaton; Trajectories and Space-Time Patterns; Basins of Attraction; Constructing and Portraying Attractor Basins; Computing Pre-Images; The Cellular Automata Reverse Algorithm; The Z Parameter; Gliders in Cellular Automata; Input-Entropy; Ordered Dynamics; Complex Dynamics; Chaotic Dynamics; Filtering; Entropy-Density Signatures; Automatically Classifying Rule-Space; Attractor Basin Measures; Glider Interactions and Basins of Attraction; The DDLab Software)

ANDREW ADAMATZKY: New Media for Collision-Based Computing (Molecular Chains; Molecular Array Processors; Bulk Media Processors; Liquid-Crystal Processors; Granular-Material Processors; Reaction-Diffusion Processors; Automata Models of Computing with Localizations; Automata Solitons; Models of Molecular Chains; Models of Molecular Arrays; Automata Worms; Excitable Lattices and Reaction-Diffusion)

LEONID A. BUNIMOVICH, MILENA A. KHLABYSTOVA: Lorentz Lattice Gases and Many-Dimensional Turing Machines (Dynamical Models of Turing Machines; General Properties of Lorentz Lattice Gases, LLG; Description of Models; Regular Lattices; Delaunay Random Lattice; LLG with Fixed Scatterers; LLG with Flipping Scatterers; Flipping LLG with One Moving Particle; Flipping LLG with Infinitely Many Moving Particles)

ENRICO PETRAGLIO, GIANLUCA TEMPESTI, JEAN-MARC HENRY: Arithmetic Operations with Self-Replicating Loops (Self-Replicating Cellular Automata; Von Neumann's Automaton; Langton's Loop; The New Automaton; Cellular Space and Initial Configuration; Operation; Collision-Based Computing; Binary Addition; Binary Multiplication; Implementation on Self-Replicating Loops; Addition; Multiplication; Combinations of Multiplication and Addition)

JEAN-PHILIPPE RENNARD: Implementation of Logical Functions in the Game of Life (Logical Gates; Collision Reactions; Glider Collisions; Eaters; Implementation of Logical Gates; AND-Gate; OR-Gate; NOT-Gate; Implementation of Boolean Equations; Management of the NOT-Gate; Binary Adder)

PAUL RENDELL: Turing Universality of the Game of Life (Some Game of Life Patterns; Adder; Sliding Block Memory; Memory Cell; Construction of the Turing Machine; The Finite State Machine; Selection of a Row; Selection of a Column; Set Reset Latch; Collecting Data from the Memory Cell; The Tape; Coupling the Finite State Machine with the Stacks; Extending the Pattern to Make a Universal Turing Machine)

Table of contents

Michael Conrad and Klaus-Peter Zauner

Conformation-Based Computing: A Rationale and a Recipe


Tanya Sienko and Jean-Marie Lehn: 

Molecular Recognition: Storage and Processing of Molecular Information                                                                                 


Andrew Adamatzky

Computing in Reaction-Diffusion and Excitable Media: Case Studies of Unconventional Processors


Nicholas G. Rambidi

Chemical-Based Computing and Problems of High Computational

Complexity: The Reaction-Diffusion Paradigm


Carlo C. Maley

DNA Computing and Its Frontiers


Duane L. Marcy, Bryan W. Vought, and Robert R. Birge

Bioelectronics and Protein-Based Optical Memories and Processors           


Satoshi Sasaki and Isao Karube

Bioelectronics and Biocomputers





The MIT Press






















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 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 studies 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.