[(Collision-based Computing )] [Author: Andrew I. Adamatzky] [Aug-2002]

by Andrew Adamatzky

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 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 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 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 Nu

Unknown Binding

First published June 20, 2002