\(
\newcommand{\llbracket}{[\![}
\newcommand{\rrbracket}{]\!]}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ACA}{\mathcal{A}}
\newcommand{\ACC}{\mathcal{C}}
\newcommand{\ACV}{\mathcal{V}}
\newcommand{\ACQ}{\mathcal{Q}}
\)
Présentation du cours
Cours M2 - MIT
Victor Poupet
À propos du cours
Thématiques liées à la notion théorique de calcul (thèmes de recherche de l’équipe Escape du LIRMM) :
- Modèles de calcul
- Systèmes dynamiques
- Décidabilité
- Complexité
Responsable : Victor Poupet
Modèles de calcul
- On veut définir formellement la notion de calcul
- On veut prouver des résultats sur les capacités des ordinateurs (ce qu’ils peuvent ou ne peuvent pas faire)
Mais les ordinateurs réels sont trop complexes et évoluent trop vite pour faire des preuves.
On s’intéresse à des objets théoriques très simples à définir mais capables d’exécuter des programmes complexes : modèles de calcul
- machine de Turing
- automates cellulaires
- jeux de tuiles (pavages du plan)
- machines à compteurs
- etc.
Exemples
Formalisation de l’idée de calcul à partir des années 1920
- Fonctions récursives primitives
- Fonctions partielles récursives (schéma \(\mu\))
- Lambda calcul
- Machines de Turing
- Machines RAM
- Machines à compteurs
- Automates cellulaires
Équivalence des définitions de fonctions (partielles) récursives
→ thèse de Church-Turing
Systèmes dynamiques
Les systèmes dynamiques sont des objets mathématiques sur lesquels on définit une évolution au cours du temps
- Espace des configurations
- Configuration initiale
- Règle d’évolution
→ Dynamique temporelle
Systèmes dynamiques
Exemples :
- Machines de Turing
- Automates cellulaires
- Conjecture de Collatz
- Systèmes dynamiques continus (équations différentielles)
Questions à propos du comportement temporel
- Périodicité
- Nilpotence
- Convergence
- Apparition d’une propriété particulière
- Sensibilité aux conditions initiales (chaos)
Différence de point de vue
Les modèles de calculs et les systèmes dynamiques sont très liés
- La plupart des systèmes dynamiques intéressants sont des modèles de calcul
- La plupart des modèles de calcul définissent une évolution temporelle, ce sont donc des systèmes dynamiques
→ Deux problématiques distinctes sur les mêmes objets.
Remarque : En général on montre qu’un système dynamique a un comportement complexe en encodant du calcul.
Contenu du cours
Deux objets en particulier (fortement liés) :
- Automates cellulaires
- Fonctionnement général
- Topologie
- Décidabilité des propriétés dynamiques
- Pavages
- Propriétés de base
- Décidabilité
- Pavages complexes
Historique
- 1940s. J. von Neumann et S. Ulam étudient les systèmes auto-reproductifs
- 1940s. Modélisations de systèmes physiques (cristaux) et biologiques (transmissions de signaux)
- 1960s. Définition en tant que système dynamique symbolique (G. A. Hedlund) → caractérisation topologique des AC
- 1960s. Algorithmes de calcul (ex. Fischer)
- 1971. Turing-complétude (A. R. Smith)
Définition
Un automate cellulaire (AC) est un quadruplet \(\ACA = (d,\ACQ, \ACV, \delta)\) où :
- \(d \in \NN\) est la dimension
- \(\ACQ\) est un ensemble fini d’états
- \(\ACV \subset \ZZ^d\) est le voisinage
- \(\delta : \ACQ^\ACV \rightarrow \ACQ\) est la fonction locale de transition
→ Évolution dynamique (temps discret)
On applique la règle locale à toutes les cellules simultanément
Caractéristiques :
- Finiment définissable
- Synchrone
- Mémoire finie par cellule
- Uniforme
- Local
Un célèbre exemple
Le jeu de la vie inventé par J. H. Conway
- \(d=2\)
- \(\ACQ = \{0, 1\}\) (vide, vivant)
- voisinage de Moore (8 voisines)
- règle locale :
- une cellule reste vivante si elle a 2 ou 3 autres voisines vivantes
- une nouvelle cellule apparaît dans une case vide ayant 3 voisines vivantes
- dans les autres cas, la case devient vide.
http://golly.sourceforge.net
Diagramme espace-temps
En dimension 1, on peut représenter les configurations successives sur un diagramme espace-temps
Vitesse de propagation
Voisinage fini → vitesse de propagation de l’information bornée
- cône d’influence futur : sites potentiellement affectés par un site particulier
- cône d’influence passé : sites pouvant affecter un site particulier
Configurations finies
Soit \(\ACA = \{d, \ACQ, \ACV, \delta\}\) un AC
Def.
Un état \(q \in \ACQ\) est quiescent si \[\delta(q, \ldots, q) = q\]
Def.
Étant fixé un état quiescent \(q_0\), une configuration \(\ACC\) est dite finie si le nombre de cellules dans un état autre que \(q_0\) est fini
Prop.
L’image d’une configuration finie est finie
Attention : Les antécédents d’une configuration finie peuvent être infinis
Signaux
- Interprétation de déplacements d’états : signaux
- Interaction entre les signaux
- Possibilité de réaliser des signaux de vitesse variable
- Algorithmique à base de signaux
