zbMATH — the first resource for mathematics

Decidability and universality in symbolic dynamical systems. (English) Zbl 1114.03032
An effective symbolic space is a pair \((X,P)\) where \(X\) is a symbolic space and \(P\colon \mathbb N \to 2^X\) is an injective function whose range is the set of all clopen sets of \(X\). An effective symbolic dynamical system is a symbolic space with continuous self-map in which intersections, complements and inverse images of clopen sets are computable. A shift is dynamical system on \(A^{\mathbb N}\) or \(A^{\mathbb Z}\) (\(A\) is a finite alphabet) with map \(\sigma\) such that \(\sigma(x)_i=x_{i+1}\). A subshift is a closed subset of a shift which is invariant under the shift map.
A general definition for computational universality that applies to arbitrary discrete-time symbolic dynamical systems is proposed in this article. An effective dynamical system is universal if the finite-time observation problem of the system is recursively-enumerable complete. It is proved that a universal system is not decidable. A system is called decidable if there is an algorithm for deciding the infinite-time observation problem. For Turing machines, counter machines and tag systems this definition of universality coincides with the classical one, but for cellular automata and subshifts it yields a new definition. There are several results proved in the article, for example, the decidability of the minimal dynamical system and the decidability of the effective regular system. On the other hand, an example of a regular and universal system is given. Further, the shadowing property and equicontinuity are studied; for both effectiveness yields decidability. Finally, an effective system on the Cantor space such that it is chaotic and universal is given using Turing machines.

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