Abstract Geometrical Computation 10: An Intrinsically Universal Family of Signal Machines
Preprint
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Symbolic dynamics of glider guns for some one-dimensional cellular automataNonlinear Dynamics, 2016
- Intrinsic universality in tile self-assembly requires cooperation2013
- Intrinsic universality and the computational power of self-assemblyElectronic Proceedings in Theoretical Computer Science, 2013
- The Tile Assembly Model is Intrinsically Universal2012
- Partitioned quantum cellular automata are intrinsically universalNatural Computing, 2011
- Communication complexity and intrinsic universality in cellular automataTheoretical Computer Science, 2011
- Abstract geometrical computation 3: black holes for classical and analog computingNatural Computing, 2009
- Universality in Elementary Cellular AutomataComplex Systems, 2004
- Signals in one-dimensional cellular automataTheoretical Computer Science, 1999
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989