|
|
 |
|
Vendredi 11 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 ? (2e 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. |
|
|
