Selfsimilarity, Simulation and Spacetime Symmetries

We study intrinsic simulations between cellular automata and introduce a new necessary condition for a CA to simulate another one. Although expressed for general CA, this condition is targeted towards surjective CA and especially linear ones. Following the approach introduced by the first author in an earlier paper, we develop proof techniques to tell whether some linear CA can simulate another linear CA. Besides rigorous proofs, the necessary condition for the simulation to occur can be heuristically checked via simple observations of typical space-time diagrams generated from finite configurations. As an illustration, we give an example of linear reversible CA which cannot simulate the identity and which is 'time-asymmetric', i.e. which can neither simulate its own inverse, nor the mirror of its own inverse.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00649749
Author Nesme, Vincent, Theyssier, Guillaume
Maintainer CCSD
Last Updated November 10, 2026, 18:32 (UTC)
Created November 10, 2026, 18:32 (UTC)
Identifier hal-00649749
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Quantum Information Theory ; University of Potsdam = Universität Potsdam
creator Nesme, Vincent
date 2011-07-10T00:00:00
harvest_object_id 1551903a-c5f5-430d-b791-51cdf565f787
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-09-27T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1112.1933
set_spec type:UNDEFINED