Decidability in continuous time dynamical systems

Slides

Dynamical systems allow to describe various processes (such as trajectories, natural phenomena, computations) by the space on which it happens, its dynamics and its initial configuration. Such a description is enough to define the whole evolution of the system but gives no idea of its whole behaviour. It is often crucial for some systems to check various properties on the whole trajectory such as deciding whether it enters a certain configuration, it reaches a given region or it collapses.

We will define the canonical problems for continuous-time dynamical problems and show that in general dynamical systems, those problems are undecidable. We will see that even very restrictive classes exhibit a computation power similar to that of Turing machines and hence in which the interesting problems are undecidable. We will also show that for the class of linear dynamical systems, some of the problems are decidable.

This document was translated from L^AT_EX by H^EV^EA.