zbMATH — the first resource for mathematics

Computational universality in symbolic dynamical systems. (English) Zbl 1102.03304
Margenstern, Maurice (ed.), Machines, computations, and universality. 4th international conference, MCU 2004, Saint Petersburg, Russia, September 21–24, 2004. Revised selected papers. Berlin: Springer (ISBN 3-540-25261-4/pbk). Lecture Notes in Computer Science 3354, 104-115 (2005).
Summary: Many different definitions of computational universality for various types of systems have flourished since Turing’s work. In this paper, we propose a general definition of universality that applies to arbitrary discrete time symbolic dynamical systems. For Turing machines and tag systems, our definition coincides with the usual notion of universality. It however yields a new definition for cellular automata and subshifts. Our definition is robust with respect to noise on the initial condition, which is a desirable feature for physical realizability.
We derive necessary conditions for universality. For instance, a universal system must have a sensitive point and a proper subsystem. We conjecture that universal systems have an infinite number of subsystems. We also discuss the thesis that computation should occur at the ‘edge of chaos’ and we exhibit a universal chaotic system.
For the entire collection see [Zbl 1067.68007].

03D10 Turing machines and related notions
37B10 Symbolic dynamics
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI