Hierarchy of Discrete-Time Dynamical Systems, a Survey.
Frédéric Geurts · 1995
This paper is an attempt to unify classical automata theory and dynamical systems theory. We present a notion of generalized dynamical systems, allowing us to compare properties of both types of systems. Then we establish a hierarchy of dynamical systems, including Turing machines, cellular automata and classical dynamical systems. We finish with some conclusions and motivations for future work. 1 Introduction The theory of finite automata has always been an important field of computer science. Automata, languages, grammars, have been extensively studied [16, 20, 43]. Automata recognize languages and grammars produce languages. Among others, the most studied are finite automata, pushdown automata, Turing machines. The Chomsky hierarchy for languages and grammars is also very well established: regular, context-free, context-sensitive, general grammars generate languages with the same names. The theory of dynamical systems, chaos, attractors [8, 41], is an important field of mathematics...