Abstract Geometrical Computation 9: Exact Discretization of 3-Speed Rational Signal Machines
Tom Besson and Jérôme Durand-Lose
In the context of abstract geometrical computation, signal machines have been developed as a continuous counterpart of cellular automata capturing the notions of particles, signals and collisions. An important issue is the automatic generation of a CA mimicking the dynamics of a given signal machine. On the one hand, ad hoc/manual conversions exist. On the other hand, it is not always possible since some signal machines exhibit behaviors (like fractal constructions or relying on an unbounded density of information) that are just impossible with (discrete) cellular automata.
This article provides a solution to automatically generate a cellular automata for a “maximal” class of signal machines that cannot exhibit such behaviors. This scheme encompasses the discretization of initial configuration so that the original continuous dynamics and the discrete one generated are identical up to a linear deformation. The considered signal machines are the ones that use only three speeds and allow only rational speeds and initial positions. Signals in these machines are always trapped inside a regular mesh. The construction relies on generating the corresponding discrete mesh. The soundness of the construction is proved and experimental results are provided.
Keywords: Abstract geometrical computation; automatic discretization; cellular automata; signal machines.