|
|
 |
|
Vendredi 31 Mars
| Heure: |
11:00 - 12:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Équivalences entre programmes |
| Description: |
Jean-Yves Moyen Partant du théorème de Rice, on définit l'équivalence extensionelle comme "deux programmes sont équivalents si ils calculent la même fonction." Le théorème de Rice stipule alors une indécidabilité forte de cette équivalence (aucune union de classes n'est décidable).
Qu'en est-il des autres équivalences entre programmes ? Certaines sont décidables (eg, avoir le même nombre de lignes de codes), d'autres non. L'ensemble des équivalences possède une structure de treillis complet et le théorème de Rice parle de l'indécidabilité d'un filtre principal de ce treillis.
À partir de ces constatations, j'explore deux pistes parallèles. D'une part, quelle est l'importance de l'équivalence extensionelle dans ces résultats ? Est-ce qu'on peut obtenir d'autres résultats similaires à partir d'une autre équivalence ? D'autre part, comment étudier l'ensemble du treillis des équivalences ? Est-ce qu'on peut trouver des sous-ensembles qui conservent la structure lié à l'ordre tout en étant plus facilement manipulables (notamment, dénombrables) ? |
|
|
