Affordable Access

Abstract Geometrical Computation 10: An Intrinsically Universal Family of Signal Machines

Authors
  • Becker, Florent
  • Besson, Tom
  • Durand-Lose, Jérôme
  • EMMANUEL, AURÉLIEN
  • FOROUGHMAND-ARAABI, MOHAMMAD-HADI
  • GOLIAEI, SAMA
  • Heydarshahi, Shahrzad
Publication Date
Jan 01, 2021
Source
HAL
Keywords
Language
English
License
Unknown
External links

Abstract

Signal machines form an abstract and idealised 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 which 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, 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 set of speeds S and their corresponding simulators provides an intrinsically universal family of signal machines.

Report this publication

Statistics

Seen <100 times