Decidability and Universality in Symbolic Dynamical Systems

Simple item page
dc.creatorDelvenne, Jean-Charles
dc.creatorKurka, Petr
dc.creatorBlondel, Vincent
dc.date2004-04-08
dc.date2005-07-08
dc.date.accessioned2026-07-07T03:21:06Z
dc.date.available2026-07-07T03:21:06Z
dc.descriptionMany different definitions of computational universality for various types of dynamical systems have flourished since Turing's work. We propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. Universality of a system is defined as undecidability of a model-checking problem. For Turing machines, counter machines and tag systems, our definition coincides with the classical one. It yields, however, a new definition for cellular automata and subshifts. Our definition is robust with respect to initial condition, which is a desirable feature for physical realizability. We derive necessary conditions for undecidability and universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have infinite number of subsystems. We also discuss the thesis according to which computation should occur at the `edge of chaos' and we exhibit a universal chaotic system.
dc.description23 pages; a shorter version is submitted to conference MCU 2004 v2: minor orthographic changes v3: section 5.2 (collatz functions) mathematically improved v4: orthographic corrections, one reference added v5:27 pages. Important modifications. The formalism is strengthened: temporal logic replaced by finite automata. New results. Submitted
dc.identifierhttps://arxiv.org/abs/cs/0404021
dc.identifierhttp://arxiv.org/abs/cs/0404021
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32071
dc.subjectComputational Complexity
dc.subjectLogic in Computer Science
dc.subjectF.1.1; F.4.1
dc.titleDecidability and Universality in Symbolic Dynamical Systems
dc.typetext

Files

Collections

arXiv