Exact discretization of 3-speed rational signal machines - Cellular Automata and Discrete Complex Systems
Conference Papers Year : 2016

Exact discretization of 3-speed rational signal machines

Abstract

Cellular Automata (CA) operate in discrete time and space whereas Signal Machines (SM) have been developed as a continuous idealization of CA capturing the key concept of signals/particles and collisions. Inside a Euclidean space, dimensionless signals move freely; collisions are instantaneous. Today's issue is the automatic generation of a CA mimicking a given SM. On the one hand, many ad hoc manual conversions exist. On the other hand, some irrational or 4+-speed SM exhibit Zeno-like behaviors/space-time compression or rely on information being locally unbounded, both being incompatible with CA. This article provides a solution to automatically generate an exactly mimicking CA for a restricted class of SM: the ones that uses only three rational speeds, and rational initial positions. In these SM, signals are always contained inside a regular mesh. The discretization brings forth the corresponding discrete mesh. The simulation is valid on any infinite run and preserves the relative position of collisions.
Fichier principal
Vignette du fichier
395687_1_En_6_Chapter.pdf (518.32 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01298378 , version 1 (13-01-2017)

Licence

Identifiers

Cite

Tom Besson, Jérôme Durand-Lose. Exact discretization of 3-speed rational signal machines. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. pp.63-76, ⟨10.1007/978-3-319-39300-1_6⟩. ⟨hal-01298378⟩
222 View
122 Download

Altmetric

Share

More