|
|
Complexity and Computational Capacity of Discrete Dynamical Systems
Hudcová, Barbora ; Mikolov, Tomáš (advisor) ; Aubrun, Nathalie (referee) ; Kupsa, Michal (referee)
The central aim of this thesis is to study the concepts of "complexity" and "com- putational capacity" of discrete dynamical systems and to connect them to rigorously measurable properties. In the first part of the thesis, we propose a formal metric of a dis- crete system's complexity based on the numerical estimates of its asymptotic convergence time. We identify a critical region of systems corresponding to a phase transition from an ordered to a chaotic phase. Additionally, we complement this work by studying dynam- ical phase transitions of discrete systems analytically, using newly developed tools from statistical physics. Specifically, for a fixed discrete system, we demonstrate that varying its initial configurations can result in abrupt changes in the system's behaviour; and we describe exact positions of such transitions. The second part of this thesis is dedicated to analysing computational capacity of cellular automata via the notion of their relative simulation. Informally, we say that automaton B can simulate A if B can effectively reproduce any dynamics of A. We introduce a specific notion of automata simulation and formalize it in algebraic language. This allowed us to answer open questions about the computational capacity of cellular automata using well-established algebraic results. Namely,...
|
guest ::
