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

https://hal.archives-ouvertes.fr/hal-01298378
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

File

395687_1_En_6_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

280

Files downloads

24