Paper Info
Title
An Intrinsically Universal Family of Signal Machines.
Abstract
Signal machines form an abstract and perfect model of collision computing as well as particle/signal/soliton dynamics in cellular automata based on dimensionless signals on a line. Each signal move at constant speed (according to its nature). When signals meet they get replaced by other signals. A signal machine defines the kind of signals available, their speeds and the rules for replacement. Given any finite set of speeds S, we prove that there exists a signal machine able to simulate any signal machine whose speeds belong to S. Each signal is simulated by a large macro-signal (ray of parallel signals inside a support zone). Each macro-signal has a main signal located exactly where the simulated signal would be and encodes its id and the rules of the simulated machine. The simulation of a collision (macro-collision) consists of two phases. In the first phase, macro-signals are shrunk-to get some delay-then involved macro-signals are identified and it is ensured that no other macro-signal is too close. If not, the process is aborted and the relative distance between shrunk macro-signals was enlarge so that the correct macro-collision will eventually be initiated. Otherwise, the second phase starts: the appropriate rule is found and new macro-signals are generated accordingly. Varying the set of speeds generates an intrinsically universal family of signal machines.
Year
Venue
Field
2018
arXiv: Formal Languages and Automata Theory
Soliton,Cellular automaton,Topology,Discrete mathematics,Finite set,Existential quantification,Collision,Mathematics,Dimensionless quantity
DocType
Volume
Citations 
Journal
abs/1804.09018
0
PageRank 
References 
Authors
0.34
6
4
Name
Order
Citations
PageRank
Florent Becker100.34
Jérôme Durand-Lose212714.93
Mohammad-Hadi Foroughmand-Araabi342.82
Sama Goliaei4297.98