|
![](images/spacer.gif) |
Vendredi 18 Octobre
Heure: |
10:00 - 12:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Intensionnalité vs. extensionnalité : où est-elle la frontière ? (3e partie) |
Description: |
Jean-Yves Moyen Au cours de ces trois séances de groupe de travail, je ferai le "débriefing" de mon CRCT et je vous présenterai les résultats obtenus à Nancy en collaboration avec Guillaume Bonfante et Pierre, ou à Copenhague en collaboration avec James Avery et Jakob Simonsen (qui sera par ailleurs prof invité chez nous en février).
Au gré de vos interruptions et de nos discussions, nous parlerons sans doute de Rice et de Gödel, de cardinaux et de grands ordinaux, d'ordre supérieur et de non déterminisme, de treillis, de partitions, peut-être de topologie. Les catégoriciens pourront s'exercer à faire commuter des diagrammes. Ne reniant pas mes origines, tout cela sera enrobé dans une couche de complexité implicite.
Le point de départ est une relecture du théorème de Rice entamée avec Pierre il y a quelques années. Au lieu de parler de "propriétés extensionnelles", le résultat est vu comme parlant de l'équivalence extensionnelle (p et q sont équivalents si ils calculent la même fonction). Autrement dit, on quotiente l'ensemble des programmes par leur extension.
Cette vision fait de Rice une équivalence parmi d'autres et on peut chercher d'autres équivalences "intéressantes" entre programmes. Notamment, l'ensemble des équivalences formant un treillis complet, on peut étudier ce treillis. |
|
|