# Decidability and Undecidability in Dynamical Systems

1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : A computing system can be modelized in various ways: one being in analogy with transfer functions, this is a function that associates to an input and optionally some internal states, an output ; another being focused on the behaviour of the system, that is describing the sequence of states the system will follow to get from this input to produce the output. This second kind of system can be defined by dynamical systems. They indeed describe the local'' behaviour of a system by associating a configuration of the system to the next configuration. It is obviously interesting to get an idea of the global'' behaviour of such a dynamical system. The questions that it raises can be for example related to the reachability of a certain configuration or set of configurations or to the computation of the points that will be visited infinitely often. Those questions are unfortunately very complex: they are in most cases undecidable. This article will describe the fundamental problems on dynamical systems and exhibit some results on decidability and undecidability in various kinds of dynamical systems.
Keywords :
Type de document :
Rapport
[Research Report] 2009, pp.27
Domaine :

Littérature citée [16 références]

https://hal.inria.fr/inria-00429965
Contributeur : Emmanuel Hainry <>
Soumis le : jeudi 5 novembre 2009 - 13:33:46
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : mardi 16 octobre 2012 - 13:20:15

### Fichier

dynsys.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00429965, version 1

### Citation

Emmanuel Hainry. Decidability and Undecidability in Dynamical Systems. [Research Report] 2009, pp.27. 〈inria-00429965〉

### Métriques

Consultations de la notice

## 277

Téléchargements de fichiers