Computer orbits for Discrete Dynamical Systems – CODYS
Computer orbits of dynamical systems
This project focuses on the orbits (i.e., trajectories under the action of the system) of discrete-time dynamic systems that are relevant to computer science. Since, very roughly speaking, computers only process finite data, they only see periodic orbits.
We consider two main types of discrete orbits:<br /><br /> -finite and periodic orbits (these orbits generally have an arithmetic meaning for the systems we are considering and form a countable set),<br />-orbits for discretizations of dynamical systems (the discretization being generally performed with respect to a finite space).
We will address two types of questions about discrete orbits in the project:
Accessibility problems will be addressed by focusing on the construction of invariants and special orbits, and the long-term behaviour of orbits, considering the ergodic and probabilistic behaviour of truncated orbits.
This four-year project is divided into five tasks.
We address the issue of genericity from various points of view in the GEN Task.
Task PER is devoted to the study of finite and periodic orbits, describes their characteristics and compares them to the orbits of the initial system.
Discretization is considered in Task DIS, with simulation as the motivation.
Simulation is at the heart of Task SIM, oriented towards numerical computation but also towards the study of dynamic systems as computational models.
The Task SPE is dedicated to the construction of special orbits and invariants.
Translated with www.DeepL.com/Translator (free version)
We efficiently construct special orbits and invariants, and study the asymptotic statistical behaviour of a dynamic system, both computationally and effectively.
One of the main motivations for this project comes from simulation. We want to develop a common formalism for the study of different types of natural discretizations motivated by simulation. The dynamic system (X,T) is associated with a sequence of discretizations that depend on a parameter N (related to the number of points in the discretization space). The project aims to describe the asymptotic behaviour of these systems. Will this asymptotic behaviour be «close« to that of the initial system? Or, will it completely forget the initial system and behave like a random finite dynamic system? More precisely, we focus on the study and comparison of discrete orbits (finite, periodic and discrete orbits). We address the question of the relevance of ergodic and dynamic methods for their study and, more generally, for simulation. We plan to develop a theoretical and practical study of discretization and simulation for simple systems such as interval or linear applications.
Dynamical systems have widely proved their usefulness for the modeling
of physical processes. Indeed, dynamical systems model the evolution of systems whose components interact in a simple way, allowing to go from a local property to some global
behavior. But they also
model numerous phenomena from the digital world, in deep connection with algorithmics: dynamical systems can model the execution of an algorithm, as well as
a loop in a program as the action of a multidimensional linear map.
More precisely, a discrete-time dynamical system
is defined as the action
of a map T acting on a space X (usually assumed to be compact).
One then studies the evolution of the system, in discrete time steps. The evolution of the system when starting with a point x in X (an initial condition) is then described by the orbit (i.e., the trajectory) of the point x.
The focus of this project is on orbits (that is, trajectories under the action of the system) of discrete-time dynamical systems that are relevant in computer science. Since, roughly speaking, computers handle only finite data, they only see periodic orbits. We thus consider two main types of discrete orbits: finite and periodic orbits (these orbits have usually an arithmetic meaning for the systems we consider and form a countable set), and orbits for discretizations of dynamical systems (with the discretization usually being performed with respect to a finite space).
We will tackle two types of questions on discrete orbits in the project: reachability and long-terme behavior.
Reachability problems will be handled by focusing on the construction of special invariants and orbits,
and long-term behavior of orbits, by considering the ergodic and probabilistic behavior of truncated orbits.
A main motivation comes from simulation issues. We want to develop a common formalism for the study of various types of natural discretizations, motivated by simulation. We associate with the dynamical system (X,T) a sequence of discretizations which depend on a parameter N (related to the number of points of the discretization space). The project aims at describing the asymptotic behavior of these systems. Is it true that this asymptotic behavior will be ‘close’ to the one of the initial system, and reminiscent of it? or, does it completely forget the initial system and behaves as a random finite dynamical system?
More precisely, we will focus on the study and comparison of discrete orbits (finite, periodic, and orbits of discretizations). We address the question of the relevance of ergodic and dynamical methods for their study, and more generally, for simulation.
We plan to develop both a theoretical and practical study of discretization and simulation for simple systems like expanding maps of the interval or linear maps.
We will construct in an effective way special orbits and invariants, and study the asymptotic statistical behavior of a dynamical system, from a computability and effective perspective.
To achieve this goal, this four-year project will be divided into five tasks.
We address the question of genericity and randomness from various viewpoints in Task GEN.
Task PER is devoted to the study of finite and periodic orbits, it describes their characteristics, and compares them to the orbits of the initial system.
Discretization is considered in Task DIS, with a view toward
simulation which is the core of Task SIM, directed toward numerical computing but also toward the study of dynamical systems as computing models. Task SPE is devoted
to algorithmic checkability of properties, together with the construction of special orbits and invariants for dynamical systems.
Madame Valerie BERTHE (Institut de Recherche en Informatique Fondamentale)
The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.
LaBRI Laboratoire Bordelais de Recherche en Informatique
IRIF Institut de Recherche en Informatique Fondamentale
Help of the ANR 369,754 euros
Beginning and duration of the scientific project: October 2018 - 48 Months