Je sais que la complexité de la plupart des variétés de calculs lambda typés sans la primitive combinateur Y est bornée, c'est-à-dire que seules les fonctions de complexité bornée peuvent être exprimées, la borne devenant plus grande à mesure que l'expressivité du système de types croît. Je...
Le CoC serait le point culminant des trois dimensions du Lambda Cube. Cela ne m’apparaît pas du tout. Je pense que je comprends les dimensions individuelles, et la combinaison de deux semble entraîner une union relativement simple (peut-être que je manque quelque chose?). Mais quand je regarde le...
Existe-t-il un calcul lambda typé où la logique correspondante sous la correspondance de Curry-Howard est cohérente et où il existe des expressions lambda typables pour chaque fonction calculable? Il s'agit certes d'une question imprécise, dépourvue d'une définition précise du «calcul lambda typé»....
J'ai eu une discussion avec un ami récemment (qui est un défenseur des langues fortement typées). Il a fait le commentaire: Les inventeurs de Lambda Calculus ont toujours voulu le taper. Maintenant , nous pouvons voir que l' église a été associée à la simplement dactylographié Calcul Lambda . En...
Klop, van Oostrom et de Vrijer ont un article sur le calcul lambda avec des motifs. http://www.sciencedirect.com/science/article/pii/S0304397508000571 Dans un certain sens, un modèle est un arbre de variables - bien que je ne le considère que comme un tuple imbriqué de variables, par exemple, ((x,...
Quelle est la relation entre le calcul lambda simplement typé et la logique d'ordre supérieur? Sous Curry-Howard, il semble que le calcul lambda simplement typé correspond à la logique propositionnelle. Comment est-il lié à une logique d'ordre supérieur? Selon ce tutoriel de Geuvers:...
Je suis conscient que le calcul des constructions est en train de normaliser fortement, ce qui signifie que chaque expression a une normale pour laquelle elle ne peut pas être bêta, eta-réduite davantage. Il s'agit donc en fait de l'expression la plus efficace qui calcule la même valeur que...
Le terme inversion de programme a plusieurs nuances de sens, mais a probablement commencé avec le travail de J. McCarthy de 1956, The Inversion of Functions Defined by Turing Machines dans le contexte de l'IA. À présent, de nombreuses connexions entre l'inversion de programme et d'autres domaines...
Je suis dans une situation où je dois montrer que la vérification de typage est décidable pour un calcul typé de manière dépendante sur lequel je travaille. Jusqu'à présent, j'ai pu prouver que le système est en train de normaliser fortement, et donc que l'égalité définitionnelle est décidable....
J'ai du mal à comprendre la preuve d'une forte normalisation pour le calcul des constructions. J'essaye de suivre la preuve dans le papier de Herman Geuvers "Une preuve courte et flexible de Normalisation Forte pour le Calcul des Constructions". Je peux bien suivre le raisonnement principal....