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

摘要

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 25 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.