Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Correspondance de Curry-Howard
Résumé
La correspondance de Curry-Howard, appelée également isomorphisme de Curry-de Bruijn-Howard, correspondance preuve/programme ou correspondance formule/type, est une série de résultats à la frontière entre la logique mathématique, l'informatique théorique et la théorie de la calculabilité. Ils établissent des relations entre les démonstrations formelles d'un système logique et les programmes d'un modèle de calcul. Les premiers exemples de correspondance de Curry-Howard remontent à 1958, lorsque Haskell Curry remarqua l'analogie formelle entre les démonstrations des systèmes à la Hilbert et la logique combinatoire, puis à 1969, quand William Alvin Howard remarqua que les démonstrations en déduction naturelle intuitionniste pouvaient formellement se voir comme des termes du lambda-calcul typé.
La correspondance de Curry-Howard a joué un rôle important en logique, car elle a établi un pont entre théorie de la démonstration et informatique théorique. On la retrouve utilisée sous une forme ou une autre dans de très nombreux travaux allant des années 1960 à nos jours : sémantique dénotationnelle, logique linéaire, réalisabilité, démonstration automatique, etc.
La correspondance de Curry-Howard était formulée par Curry pour la logique combinatoire dès la fin des années 1940. Howard a publié en 1980 un article qui présente formellement la correspondance pour le lambda calcul simplement typé, mais il n'a fait que rendre public un document qui avait déjà circulé dans le monde des logiciens. Elle était connue indépendamment de Joachim Lambek pour les catégories cartésiennes fermées, de Girard pour le système F et de de Bruijn pour le système Automath. Au moins ces cinq noms pourraient être associés à ce concept.
Par exemple, en lambda calcul simplement typé, si on associe à chaque type de base une variable propositionnelle et que l'on associe l'implication logique au constructeur de type alors les propositions démontrables de la logique implicative minimale (où le seul connecteur est l'implication) correspondent aux types des termes clos du lambda calcul.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.