2026-07-23T21:55:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14449 2024-03-06T10:54:02Z ddc:004 open_access

Universal Gauge-Invariant Cellular Automata Arrighi, Pablo Costes, Marin Eon, Nathanaël Cellular automata Gauge-invariance Universality Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs "matter", and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a.k.a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a.k.a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pablo Arrighi and Marin Costes and Nathanaël Eon 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.9 urn:nbn:de:0030-drops-144490 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.9 eng https://creativecommons.org/licenses/by/4.0/legalcode