Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download
Contributor : Tom Besson <>
Submitted on : Friday, January 13, 2017 - 3:42:40 PM
Last modification on : Thursday, February 7, 2019 - 4:53:21 PM
Document(s) archivé(s) le : Friday, April 14, 2017 - 8:13:19 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



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⟩



Record views


Files downloads