Séance de 18 mai, Lille

Lieu: STL, Université de Lille 3, Salle Corbin (Bât. B, salle B1 661)

Nous avons le plaisir de vous annoncer la prochaîne séance de l’axe « Interactions entre logique, calcul et linguistique » du séminaire « Réflexions sur les processus de calcul, d’information et de programmation”, mercredi 18 mai 2016 à 14h, UMR 8163 STL, Université de Lille 3, Salle D. Corbin (Bât. B, salle B1 661) avec la participation de Jean-Paul Delahaye et Johan G. Granström.

Jean-Paul Delahaye (CRIStAL, Université de Lille 1), Les mesures numériques de la complexité

Mesurer la complexité des objets numériques,même en se limitant aux objets finis, est délicat et a donné lieu à de nombreuses propositions.Nous évoquerons les mesures brutes de contenu en information, certaines mesures utilisées en arithmétique, la complexité de Kolmogorov (qui est une mesure fine de « contenu en information ») et la mesure proposée par Charles Bennett : la profondeur logique de Bennett. Seule cette dernière peut être considérée comme une mesure de « contenu en structures ».

Jean-Paul Delahaye, Mesurer la complexité des objets numériques, « 1024 » Bulletin de la Société Informatique de France, n°1, pp. 35-53, septembre 2013. http://1024.labri.fr/1024-numero-1-delahaye.pdf

JP Delahaye, Complexité aléatoire et complexité organisée, Éditions Quae, 2009.

Hector Zenil, Jean-Paul Delahaye, Cedric Gaucherel, Image Characterization and Classification by Physical Complexity, Complexity, vol 17-3 pp.26-42, 2012.

Johan G. Granström (Google Research), Identity in Intuitionistic Type Theory

Intensionality, definitional equality, convertability, identity of indiscernibles, substitution, extensionality, setoids, etc., are all concepts related to the broad concept of equality in type theory. How do these concepts relate and what are the practical implications?