








CollisionBased Computing, Editor: A. Adamatzky (SpringerVerlag, 2002), XXVII, 556 pp. Softcover;
1852335408 CollisionBased Computing presents a unique overview of computation with mobile selflocalized patterns in nonlinear 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 cellularautomaton 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 selfreplicating universal computers. CollisionBased 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, NatureInspired 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 0262194872 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
informationprocessing, molecular recognition, computation in nonlinear
media, computers based on physical reactiondiffusion systems found in
chemical media, DNA computing, bioelectronics and proteinbased optical
computing, and biosensors. 


Table of contents (download PDF) TOMMASO
TOFFOLI: Symbol
Super Colliders (Cellular Automata and Lattice Gases; Heat, Ice, and Waves;
CollidingBeams Particle Accelerators; Why Aristotle Didn't Discover
Universal Gravitation; "On The Nature of the Universe") EDWARD F. FREDKIN, TOMMASO TOFFOLI: Design Principles for Achieving HighPerformance
Submicron Digital Technologies Edward (Principles of Conservative Logic;
Implementation of Conservative Logic in Concrete Computing Devices; Prospects
for Applications to SubMicron Digital Technologies; Generalities;
JosephsonEffect 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; ConservativeLogic Gates; the Fredkin Gate; ConservativeLogic
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 ConservativeLogic Circuits; Inverse of a
ConservativeLogic Network; Combinational Networks; Role of the Scratchpad
Register. TradeOff's Between Space, Time, and Available Primitives; Circuits
that Convert Argument into Result; Energy Involved in a Computation) NORMAN MARGOLUS: PhysicsLike Models of
Computation (Cellular Automata; Reversible Cellular Automata; Entropy in RCA;
Conservation Laws in SecondOrder RCA; FirstOrder 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; SpatiallyEfficient
Computation; Signal Routing; DualRail Logic; A Fredkin Gate; Implementing
the BBMCA; Signal Routing Revisited; Relativistic Cellular Automata;
SemiClassical Models of Dynamics) JEROME DURANDLOSE: Computing Inside the Billiard
Ball Model (Block Cellular Automata; Reversibility; Relations with Classical
Cellular Automata; Universality of OneDimensional 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 RCA; Spacetime Simulation; Intrinsic
SpaceTime Universality of the BBM among CA; Uncomputable Properties) KENICHI MORITA,
YASUYUKI TOJIMA, KATSUNOBU
IMAI, TSUYOSHI OGIRO:
Universal Computing in Reversible and NumberConserving TwoDimensional Cellular
Spaces (NumberConserving Reversible Cellular Automaton; Embedding Fredkin
Gate in Simple Universal TwoDimensional BitConserving Reversible
Partitioning Cellular Automata; 16State Model with Rotation and Reflection
Symmetric Rules; 16State Model with Rotation Symmetric Rules; 8State
Triangular Model; Compact Embedding of Reversible Counter Machine in
Universal NumberConserving 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 TwoDimensional 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 BoxBall 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; SpatioTemporal Soliton Logic Gates; Cascadability of
Spatial Soliton Logic Gates; Soliton Logic Gate Transfer Function;
Interaction Details; Cascaded Inverters; Cascaded 2NOR Gates) ANDREW WUENSCHE: Finding Gliders in Cellular
Automata (OneDimensional Cellular Automaton; Trajectories and SpaceTime
Patterns; Basins of Attraction; Constructing and Portraying Attractor Basins;
Computing PreImages; The Cellular Automata Reverse Algorithm; The Z
Parameter; Gliders in Cellular Automata; InputEntropy; Ordered Dynamics;
Complex Dynamics; Chaotic Dynamics; Filtering; EntropyDensity Signatures;
Automatically Classifying RuleSpace; Attractor Basin Measures; Glider
Interactions and Basins of Attraction; The DDLab Software) ANDREW ADAMATZKY: New Media for CollisionBased Computing
(Molecular Chains; Molecular Array Processors; Bulk Media Processors;
LiquidCrystal Processors; GranularMaterial Processors; ReactionDiffusion
Processors; Automata Models of Computing with Localizations; Automata
Solitons; Models of Molecular Chains; Models of Molecular Arrays; Automata
Worms; Excitable Lattices and ReactionDiffusion) LEONID A. BUNIMOVICH, MILENA A. KHLABYSTOVA: Lorentz Lattice Gases and
ManyDimensional 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, JEANMARC HENRY: Arithmetic Operations with SelfReplicating Loops (SelfReplicating
Cellular Automata; Von Neumann's Automaton; Langton's Loop; The New
Automaton; Cellular Space and Initial Configuration; Operation;
CollisionBased Computing; Binary Addition; Binary Multiplication;
Implementation on SelfReplicating Loops; Addition; Multiplication;
Combinations of Multiplication and Addition) JEANPHILIPPE RENNARD: Implementation of Logical
Functions in the Game of Life (Logical Gates; Collision Reactions; Glider
Collisions; Eaters; Implementation of Logical Gates; ANDGate; ORGate;
NOTGate; Implementation of Boolean Equations; Management of the NOTGate;
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 KlausPeter
Zauner ConformationBased Computing: A
Rationale and a Recipe Tanya Sienko and JeanMarie
Lehn: Molecular Recognition: Storage
and Processing of Molecular Information Computing in ReactionDiffusion and
Excitable Media: Case Studies of Unconventional Processors ChemicalBased Computing and
Problems of High Computational Complexity: The
ReactionDiffusion Paradigm DNA Computing and Its Frontiers Duane L. Marcy, Bryan
W. Vought, and Robert R. Birge Bioelectronics and ProteinBased
Optical Memories and Processors Satoshi Sasaki and Isao
Karube Bioelectronics and Biocomputers

























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 spatiotemporal 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 collisionbased 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 wouldbe 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 HighPerformance 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 collisionbased 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, dualrail 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 semiclassical 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 DurandLose 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 collisionbased computing. Firstly, DurandLose 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 twocounter 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 NumberConserving TwoDimensional 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. Nonclassical logical understanding of collisionbased 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 collisionbased computing: gliders, particles, automata signals, solitons and other mobile 1ocalisations in nonlinear 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 twodimensional 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 onedimensional cellular automaton that supports infinite families of signals of different speeds. Feasibility of DelormeMazoyer constructions is demonstrated in problems of multiplication in onedimensional 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 onedimensional solitons. Various designs of soliton gates are discussed in a context of massivelyparallel 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 collisionbased 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 collisionbased computing; temporal, spatial and spatiotemporal soliton logic gates are designed there. Thus, to demonstrate that soliton logical gates may form selfconsistent cascades with signal fanout, 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 cellularautomaton 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 spacetime 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 monomolecular arrays, worms in liquid crystals, groups of oscillons in vibrating granular materials and quasiparticles in reactiondiffusion systems. The phenomena are discussed in Andrew Adamatzky's chapter “New Media for CollisionBased Computing”. An illuminating comparison of logicalgate architectures realised in “real” systems and their automata models gives us a vision of what types of collisionbased computer prototypes can be built in laboratories. Particle dynamics on twodimensional 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 ManyDimensional 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. Selfreplication and universal computing is the subject of the chapter “Arithmetic Operations with SelfReplicating Loops” written by Enrico Petraglio, Gianluca Tempesti and JeanMarc Henry, who are experts in embryonic electronics, bioinspired machines and evolving hardware. In their chapter, a cellular automaton is developed that is capable of selfreplication, 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 selfreplicating 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 collisioncomputationally 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 GameofLife fans to the field of collisionbased computing. “Implementation of Logical Functions in the Game of Life” by JeanPhilippe Rennard gives a brief introduction to the subject of GameofLifebased 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, natureinspired computing, artificial intelligence, smart engineering systems, complex and adaptive systems, parallel computation, applied mathematics and computational physics. 







