Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Abstract Geometrical Computation 10

Abstract Geometrical Computation 10 Signal machines form an abstract and idealized model of collision computing. Based on dimensionless signals moving on the real line, they model particle/signal dynamics in Cellular Automata. Each particle, or signal, moves at constant speed in continuous time and space. When signals meet, they get replaced by other signals. A signal machine defines the types of available signals, their speeds, and the rules for replacement in collision. A signal machine A simulates another one B if all the space-time diagrams of B can be generated from space-time diagrams of A by removing some signals and renaming other signals according to local information. Given any finite set of speeds S we construct a signal machine that is able to simulate any signal machine whose speeds belong to S. Each signal is simulated by a macro-signal, a ray of parallel signals. Each macro-signal has a main signal located exactly where the simulated signal would be, as well as auxiliary signals that encode its id and the collision rules of the simulated machine. The simulation of a collision, a macro-collision, consists of two phases. In the first phase, macro-signals are shrunk, and then the macro-signals involved in the collision are identified and it is ensured that no other macro-signal comes too close. If some do, the process is aborted and the macro-signals are shrunk, so that the correct macro-collision will eventually be restarted and successfully initiated. Otherwise, the second phase starts: the appropriate collision rule is found and new macro-signals are generated accordingly. Considering all finite sets of speeds S and their corresponding simulators provides an intrinsically universal family of signal machines. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Abstract Geometrical Computation 10

Download PDF
31 pages

Loading next page...
 
/lp/association-for-computing-machinery/abstract-geometrical-computation-10-oboAKXbb85
Publisher
Association for Computing Machinery
Copyright
Copyright © 2021 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3442359
Publisher site
See Article on Publisher Site

Abstract

Signal machines form an abstract and idealized model of collision computing. Based on dimensionless signals moving on the real line, they model particle/signal dynamics in Cellular Automata. Each particle, or signal, moves at constant speed in continuous time and space. When signals meet, they get replaced by other signals. A signal machine defines the types of available signals, their speeds, and the rules for replacement in collision. A signal machine A simulates another one B if all the space-time diagrams of B can be generated from space-time diagrams of A by removing some signals and renaming other signals according to local information. Given any finite set of speeds S we construct a signal machine that is able to simulate any signal machine whose speeds belong to S. Each signal is simulated by a macro-signal, a ray of parallel signals. Each macro-signal has a main signal located exactly where the simulated signal would be, as well as auxiliary signals that encode its id and the collision rules of the simulated machine. The simulation of a collision, a macro-collision, consists of two phases. In the first phase, macro-signals are shrunk, and then the macro-signals involved in the collision are identified and it is ensured that no other macro-signal comes too close. If some do, the process is aborted and the macro-signals are shrunk, so that the correct macro-collision will eventually be restarted and successfully initiated. Otherwise, the second phase starts: the appropriate collision rule is found and new macro-signals are generated accordingly. Considering all finite sets of speeds S and their corresponding simulators provides an intrinsically universal family of signal machines.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Feb 10, 2021

Keywords: Abstract geometrical computation

References

  • Collision Based Computing
    (Ed, Andrew Adamatzky
  • A simple universal cellular automaton and its one-way and totalistic version
    Albert, Jürgen; II., Karel Čulik
  • Partitioned quantum cellular automata are intrinsically universal
    Arrigh, Pablo; Grattage, Jonathan
  • On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines
    Blum, Lenore; Shub, Michael; Smale, Steve
  • Particle-like structures and interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules
    Boccara, Nino; Nasser, J.; Roger, Michel
  • Universality in elementary cellular automata
    Cook, Matthew
  • Signals on cellular automata
    Delorme, Marianne; Mazoyer, Jacques
  • The tile assembly model is intrinsically universal
    Doty, David; Lutz, Jack H.; Patitz, Matthew J.; Schweller, Robert T.; Summers, Scott M.; Woods, Damien
  • Intrinsic universality in self-assembly
    Doty, David; Lutz, Jack H.; Patitz, Matthew J.; Summers, Scott M.; Woods, Damien
  • Reversible cellular automaton able to simulate any other reversible one using partitioning automata
    Durand-Lose, Jérôme
  • Abstract geometrical computation 1: Embedding Black hole computations with rational numbers
    Durand-Lose, Jérôme
  • Abstract geometrical computation and the linear Blum, Shub and Smale model
    Durand-Lose, Jérôme
  • The signal point of view: From cellular automata to signal machines
    Durand-Lose, Jérôme
  • Abstract geometrical computation 3: Black holes for classical and analog computing
    Durand-Lose, Jérôme
  • Abstract geometrical computation 6: A reversible, conservative and rational based model for black hole computation
    Durand-Lose, Jérôme
  • Communication complexity and intrinsic universality in cellular automata
    Ch, Eric Goles
  • Mechanisms of emergent computation in cellular automata
    Hordijk, Wim; Crutchfield, James P.; Mitchell, Melanie
  • When can solitons compute? Complex Systems 10, 1 (1996), 1--21
    Jakubowski, Mariusz H.; Steiglitz, Kenneth; Squier, Richard K.
  • Information transfer between solitary waves in the saturable Schrödinger equation
    Jakubowski, Mariusz H.; Steiglitz, Kenneth; Squier, Richard K.
  • Computing with classical soliton collisions
    Jakubowski, Mariusz H.; Steiglitz, Kenneth; Squier, Richard K.
  • Symbolic dynamics of glider guns for some one-dimensional cellular automata
    Jin, Weifeng; Chen, Fangyue
  • Universal computation in simple one-dimensional cellular automata
    Lindgren, Kristian; Nordahl, Mats G.
  • An intrinsically universal family of causal graph dynamics
    Martiel, Simon; Martin, Bruno
  • Inducing an order on cellular automata by a grouping operation
    Mazoyer, Jacques; Rapaport, Ivan
  • Signals in one-dimensional cellular automata
    Mazoyer, Jacques; Terrier, Véronique
  • Intrinsic universality in tile self-assembly requires cooperation
    Meunier, Pierre-Etienne; Patitz, Matthew J.; Summers, Scott M.; Theyssier, Guillaume; Winslow, Andrew; Woods, Damien
  • Computation in cellular automata: A selected review
    Mitchell, Melanie
  • Two-states bilinear intrinsically universal cellular automata
    Ollinger, Nicolas
  • The intrinsic universality problem of one-dimensional cellular automata
    Ollinger, Nicolas
  • Soliton-like dynamics of filtrons of cycle automata
    Siwak, Pawel
  • Synchronization of interacting automata
    Varshavsky, Victor I.; Marakhovsky, Vyacheslav B.; Peschansky, V. A.
  • Intrinsic universality and the computational power of self-assembly
    Woods, Damien
  • Simple new algorithms which solve the firing squad synchronization problem: A 7-states 4n-steps solution
    Yunès, Jean-Baptiste