Collision-Based Computing

ISBN-13: 9781852335403 / Angielski / Miękka / 2002 / 556 str.

A. Adamatzky; Andrew Adamatzky;Springer-Verlag

Opis

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.

Recenzje

From the reviews:

"This book contains a collection of articles on the theme of how to do computation with mobile objects or patterns in nonlinear media, as exemplified most vividly by collision-based computing. ... Each chapter in the book has its own list of references ... . This book is recommended for anyone looking for an introduction to the fascinating developing subject of collision-based computing on a non-trivial level." (Menachem Dishon, Mathematical Reviews, Issue 2007 b)

Spis treści

1 Symbol Super Colliders.- 1.1 Cellular Automata and Lattice Gases.- 1.2 Heat, Ice, and Waves.- 1.3 Colliding-Beams Particle Accelerators.- 1.4 Why Aristotle Didn’t Discover Universal Gravitation.- 1.5 “On The Nature of the Universe”.- 1.6 Conclusions.- References.- I Twenty Years Ago.- 2 Design Principles for Achieving High-Performance Submicron Digital Technologies.- 2.1 Overview.- 2.1.1 Objectives.- 2.1.2 Conceptual Framework.- 2.1.3 Organization.- 2.2 Principles of Conservative Logic.- 2.2.1 Motivations.- 2.2.2 Conservative Logic.- 2.2.3 Implementation of Conservative Logic in Concrete Computing Devices.- 2.3 Prospects for Applications to Sub-Micron Digital Technologies.- 2.3.1 Generalities.- 2.3.2 Josephson-Effect Switching.- 2.3.3 Integrated Optics.- References.- 3 Conservative Logic.- 3.1 Introduction.- 3.1.1 Physical Principles Already Contained in the Axioms.- 3.1.2 Some Physical Principles that Haven’t yet Found a Way into the Axioms.- 3.2 Conservative Logic: The Unit Wire and the Fredkin Gate.- 3.2.1 Essential Primitives for Computation.- 3.2.2 Fundamental Constraints of a Physical Nature.- 3.2.3 The Unit Wire.- 3.2.4 Conservative-Logic Gates; the Fredkin Gate.- 3.2.5 Conservative-Logic Circuits.- 3.3 Computation in Conservative-Logic Circuits; Constants and Garbage.- 3.4 Computation Universality of Conservative Logic.- 3.5 Nondissipative Computation.- 3.6 A “Billiard Ball” Model of Computation.- 3.6.1 Basic Elements of the Billiard Ball Model.- 3.6.2 The Interaction Gate.- 3.6.3 Interconnection; Timing and Crossover; the Mirror.- 3.6.4 The Switch Gate and the Fredkin Gate.- 3.7 Garbageless Conservative-Logic Circuits.- 3.7.1 Terminology: Inverse of a Conservative-Logic Network; Combinational Networks.- 3.7.2 Role of the Scratchpad Register. Trade-Offs Between Space, Time, and Available Primitives.- 3.7.3 Circuits that Convert Argument into Result. General-Purpose Conservative-Logic Computers.- 3.8 Energy Involved in a Computation.- 3.9 Other Physical Models of Reversible Computation.- 3.10 Conclusions.- References.- 4 Physics-Like Models of Computation.- 4.1 Introduction.- 4.2 Cellular Automata.- 4.3 Reversible Cellular Automata.- 4.4 Entropy in RCA.- 4.5 Conservation Laws in Second-Order RCA.- 4.6 First-Order RCA.- 4.7 The Billiard Ball Model.- 4.8 The BBM Cellular Automaton.- 4.9 Relationship of BBMCA to Conservative Logic.- 4.10 Energy in the BBMCA.- 4.11 Conclusion.- 4.12 Appendix: A Second-Order, Reversible, Universal Automaton.- References.- II The Present and the Future.- 5 Universal Cellular Automata Based on the Collisions of Soft Spheres.- 5.1 Fredkin’s Billiard Ball Model.- 5.2 A Soft Sphere Model.- 5.3 Other Soft Sphere Models.- 5.4 Momentum Conserving Models.- 5.4.1 Reflections Without Mirrors.- 5.4.2 Signal Crossover.- 5.4.3 Spatially-Efficient Computation.- 5.4.4 Signal Routing.- 5.4.5 Dual-Rail Logic.- 5.4.6 A Fredkin Gate.- 5.4.7 Implementing the BBMCA.- 5.4.8 Signal Routing Revisited.- 5.4.9 A Simpler Extension.- 5.4.10 Other Lattices.- 5.5 Relativistic Cellular Automata.- 5.6 Semi-Classical Models of Dynamics.- 5.7 Conclusion.- References.- 6 Computing Inside the Billiard Ball Model.- 6.1 Definitions.- 6.1.1 Block Cellular Automata.- 6.1.2 Reversibility.- 6.1.3 Simulation.- 6.1.4 Cellular Automata.- 6.1.5 Relations with Classical Cellular Automata.- 6.2 Universality of One-Dimensional Block Cellular Automata.- 6.3 Billiard Ball Model.- 6.3.1 Basic Encoding.- 6.3.2 Conservative Logic.- 6.3.3 Dual Encoding.- 6.3.4 Reversible Logic.- 6.4 Turing Universality of the BBM.- 6.4.1 Automaton.- 6.4.2 Counters.- 6.5 Intrinsic Universality of the BBM.- 6.5.1 Partitioned Cellular Automata.- 6.5.2 Intrinsic Universality of the BBM among R-CA.- 6.5.3 Space-time Simulation.- 6.5.4 Intrinsic Space-Time Universality of the BBM among CA.- 6.6 Uncomputable Properties.- 6.6.1 Reaching a Stable or Periodic Configuration.- 6.6.2 Reaching a (Sub-)Configuration.- References.- 7 Universal Computing in Reversible and Number-Conserving Two-Dimensional Cellular Spaces.- 7.1 Number-Conserving Reversible Cellular Automaton.- 7.2 Embedding Fredkin Gate in Simple Universal Two-Dimensional Bit-Conserving Reversible Partitioning Cellular Automata.- 7.2.1 16-State Model with Rotation and Reflection Symmetric Rules.- 7.2.2 16-State Model with Rotation Symmetric Rules.- 7.2.3 8-State Triangular Model.- 7.3 Compact Embedding of Reversible Counter Machine in Universal Number-Conserving Reversible Partitioning Cellular Automata.- 7.3.1 Reversible Counter Machine.- 7.3.2 44-State Model.- 7.3.3 34-State Model.- 7.4 Conclusion.- References.- 8 Derivation Schemes in Twin Open Set Logic.- 8.1 Derived Logical Systems.- 8.2 Twin Open Set Logic.- 8.3 Twin Open Set Logic and Classical Logic.- 8.4 Derivation Schemes in Twin Open Set Logic.- 8.4.1 Nonstandard Derivation Methods (or what to do when you can’t do modus ponens).- 8.4.2 Derivation Schemes under Nonstandard Entailment.- 8.4.3 Nonstandard Implication.- 8.5 Tautologies in Twin Open Set Logics.- 8.6 Derivation Schemes in Collision Models.- 8.7 Conclusion.- References.- 9 Signals on Cellular Automata.- 9.1 Some Initial Definitions and Comments.- 9.1.1 Signals.- 9.1.2 Signals and Grids.- 9.2 Transformations of Signals.- 9.2.1 Transforming Marks on a Cell into Some Right Signal.- 9.2.2 Some Right Signals from Some Other Ones.- 9.3 Infinite Families of Signals and Grids.- 9.3.1 Infinite Families of Signals.- 9.3.2 Computations and Grids.- 9.3.3 Infinite Families of Signals (or Waves) on Two-Dimensional Cellular Automaton.- 9.4 Conclusion.- References.- 10 Computing with Solitons: A Review and Prospectus.- 10.1 Computation in Cellular Automata.- 10.2 Particle Machines (PMs).- 10.2.1 Characteristics of PMs.- 10.2.2 The PM Model.- 10.2.3 Simple Computation with PMs.- 10.2.4 Algorithms.- 10.2.5 Comment on VLSI Implementation.- 10.2.6 Particles in Other Automata.- 10.3 Solitons and Computation.- 10.3.1 Scalar Envelope Solitons.- 10.3.2 Integrable and Nonintegrable Systems.- 10.3.3 The Cubic Nonlinear Schrödinger Equation.- 10.3.4 Oblivious and Transactive Collisions.- 10.3.5 The Saturable Nonlinear Schrödinger Equation.- 10.4 Computation in the Manakov System.- 10.4.1 The Manakov System and its Solutions.- 10.4.2 State in the Manakov System.- 10.4.3 Particle Design for Computation.- 10.5 Conclusion.- References.- 11 Iterons of Automata.- 11.1 Homogeneous Nets of Automata.- 11.2 Cellular Automata Parallel Processing of Strings.- 11.3 Linear Automaton Media Serial Processing of Strings.- 11.4 Particles of Cellular Automata.- 11.5 Filtrons of Serial Processing.- 11.6 The Automata Based on FCA Window.- 11.6.1 Jiang Model.- 11.6.2 AKT Model.- 11.6.3 FPS Filters.- 11.6.4 F Model.- 11.6.5 FM Filters.- 11.6.6 BRS Models.- 11.6.7 Soliton Automata.- 11.7 Automata of Box-Ball Systems and Crystal Systems.- 11.7.1 Ball Moving Systems.- 11.7.2 Crystal Systems.- 11.8 Conclusion.- References.- 12 Gated Logic with Optical Solitons.- 12.1 Solitons for Digital Logic.- 12.1.1 Temporal Soliton Logic Gates.- 12.1.2 Spatial Soliton Logic Gates.- 12.1.3 Spatio-Temporal Soliton Logic Gates.- 12.2 Cascadability of Spatial Soliton Logic Gates.- 12.2.1 Soliton Logic Gate Transfer Function.- 12.2.2 Interaction Details.- 12.2.3 Cascaded Inverters.- 12.2.4 Cascaded 2-NOR Gates.- 12.3 Conclusions.- References.- 13 Finding Gliders in Cellular Automata.- 13.1 One-Dimensional Cellular Automaton.- 13.2 Trajectories and Space-Time Patterns.- 13.3 Basins of Attraction.- 13.4 Constructing and Portraying Attractor Basins.- 13.5 Computing Pre-Images.- 13.5.1 The Cellular Automata Reverse Algorithm.- 13.5.2 The Z Parameter.- 13.6 Gliders in One-Dimensional Cellular Automata.- 13.7 Input-Entropy.- 13.7.1 Ordered Dynamics.- 13.7.2 Complex Dynamics.- 13.7.3 Chaotic Dynamics.- 13.8 Filtering.- 13.9 Entropy-Density Signatures.- 13.10 Automatically Classifying Rule-Space.- 13.11 Attractor Basin Measures.- 13.12 Glider Interactions and Basins of Attraction.- 13.13 Conclusion.- 13.14 The DDLab Software.- References.- 14 New Media for Collision-Based Computing.- 14.1 Molecular Chains.- 14.2 Molecular Array Processors.- 14.3 Bulk Media Processors.- 14.4 Liquid-Crystal Processors.- 14.5 Granular-Material Processors.- 14.6 Reaction-Diffusion Processors.- 14.7 Automata Models of Computing with Localizations.- 14.7.1 Automata Solitons.- 14.7.2 Models of Molecular Chains.- 14.7.3 Models of Molecular Arrays.- 14.7.4 Automata Worms.- 14.7.5 Excitable Lattices and Reaction-Diffusion.- 14.8 Conclusion.- References.- 15 Lorentz Lattice Gases and Many-Dimensional Turing Machines.- 15.1 Dynamical Models of Turing Machines.- 15.2 General Properties of Lorentz Lattice Gases (LLG).- 15.3 Description of Models.- 15.3.1 Regular Lattices.- 15.3.2 Delaunay Random Lattice.- 15.4 Some Results on LLG with Fixed Scatterers.- 15.5 LLG with Flipping Scatterers.- 15.5.1 Flipping LLG with One Moving Particle.- 15.5.2 Flipping LLG with Infinitely Many Moving Particles.- 15.6 Conclusion.- References.- 16 Arithmetic Operations with Self-Replicating Loops.- 16.1 Self-Replicating Cellular Automata.- 16.1.1 Von Neumann’s Automaton.- 16.1.2 Langton’s Loop.- 16.1.3 The New Automaton.- 16.2 Description of the Automaton.- 16.2.1 Cellular Space and Initial Configuration.- 16.2.2 Operation.- 16.2.3 Example.- 16.3 Collision-Based Computing: Theoretical Notions.- 16.3.1 Binary Addition.- 16.3.2 Binary Multiplication.- 16.4 Implementation on Self-Replicating Loops.- 16.4.1 Addition.- 16.4.2 Multiplication.- 16.4.3 Combinations of Multiplication and Addition.- 16.5 Conclusion.- References.- 17 Implementation of Logical Functions in the Game of Life.- 17.1 Basic Features of the Game of Life.- 17.2 Logical Gates.- 17.3 Collision Reactions.- 17.3.1 Glider Collisions.- 17.3.2 Eaters.- 17.4 Implementation of Logical Gates.- 17.4.1 Input.- 17.4.2 Output.- 17.5 Coupling the Components.- 17.5.1 The AND-Gate.- 17.5.2 The OR-Gate.- 17.5.3 The NOT-Gate.- 17.6 Implementation of Boolean Equations.- 17.6.1 Gates Associations.- 17.6.2 Management of the NOT-Gate.- 17.7 Binary adder.- 17.8 Conclusion.- References.- 18 Turing Universality of the Game of Life.- 18.1 Some Game of Life Patterns.- 18.1.1 Adder.- 18.1.2 Sliding Block Memory.- 18.1.3 Memory Cell.- 18.2 Construction of the Turing Machine.- 18.3 The Finite State Machine.- 18.3.1 Selection of a Row.- 18.3.2 Selection of a Column.- 18.3.3 Set Reset Latch.- 18.3.4 Collecting Data from the Memory Cell.- 18.4 The Tape.- 18.5 Coupling the Finite State Machine with the Stacks.- 18.6 The Machine in the Pattern.- 18.7 Extending the Pattern to Make a Universal Turing Machine.- 18.8 Conclusion.- References.