Decidability and Universality in Symbolic Dynamical Systems
<|reference_start|>Decidability and Universality in Symbolic Dynamical Systems: Many 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.<|reference_end|>
@article{delvenne2004decidability,
    title={Decidability and Universality in Symbolic Dynamical Systems},
    author={Jean-Charles Delvenne, Petr Kurka and Vincent Blondel},
    journal={arXiv preprint arXiv:cs/0404021},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0404021},
    primaryClass={cs.CC cs.LO}
}