Je veux juste connaître quelques exemples des fonctions qui peuvent être calculées par le calcul lambda non typé mais pas par des calculs lambda typés. Comme je suis un débutant, une réitération des informations de base serait appréciée. Merci. Edit: en tapant des calculs lambda, j'avais...
J'ai essayé d'enrouler ma tête autour du quoi, pourquoi et comment du -calculus mais je ne suis pas parvenu à comprendre "pourquoi ça marche"?λλ\lambda «Intuitivement», j'obtiens le modèle de calculabilité de Turing Machines (TM). Mais cette -abstraction me laisse juste perplexe.λλ\lambda Supposons...
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 problème de la représentation des variables liées dans la syntaxe, et en particulier celui de la substitution évitant la capture, est bien connu et a plusieurs solutions: variables nommées avec équivalence alpha, indices de Bruijn, localement sans nom, ensembles nominaux, etc. Mais il semble y...
Il est facile de regarder dans beaucoup de manuels les preuves de réduction de sujet et de forte normalisation pour le système F, aussi, il existe parfois des définitions du système F avec des paires, où (t, r) est un terme, pas seulement un encodage. La question est, quelle serait la référence...
Dans la théorie de la complexité, la définition de la complexité du temps et de l'espace fait référence à une machine de Turing universelle: resp. le nombre d'étapes avant de s'arrêter et le nombre de cellules sur la bande touchées. Compte tenu de la thèse de Church-Turing, il devrait également...
Quelle est la différence d'appeler -calculus une algèbre au lieu d'un calcul? Je pose cette question parce que j'ai lu quelque part la ligne « -calculus n'est pas un calcul mais une algèbre» (iirc, attribué à Dana Scott). Dans quel but?
Je traduis un livre sur LISP et naturellement il touche certains éléments de -calculus. Ainsi, une notion d'extensionnalité y est mentionnée aux côtés de certains modèles de -calculus, à savoir: et D ^ \ infty (oui, avec l'infini en haut). Et on dit que \ mathcal {P} _ \ omega est extensionnel...
J'ai lu des informations sur la substitution héréditaire pour le calcul lambda simple et pour le cadre logique avec des termes et des types distincts. Je me demande, existe-t-il des exemples de substitution héréditaire dans un système typé de façon dépendante avec une hiérarchie d'univers?...
La seule définition du «calcul» que je connaisse est l'étude des limites, des dérivés, des intégrales, etc. en analyse. Dans quel sens le calcul lambda (ou des choses comme le calcul mu) est-il un "calcul"? Comment est-il lié au calcul dans
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:...
Le terme λ suivant, ici sous forme normale: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Implémente un algorithme de tri pour les listes codées par église. Autrement dit, le résultat de: sort...
Extrait de l' article sur la stratégie d'évaluation sur Wikipédia: La notion de stratégie de réduction dans le calcul lambda est similaire mais distincte. Extrait de l' article sur la stratégie de réduction sur Wikipédia: Elle est similaire mais subtilement différente de la notion de stratégie...
Le terme suivant (en utilisant les index bruijn): BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0))))))))) Lorsqu'il est appliqué à un numéro d'église, il prend Nrapidement sa forme normale dans plusieurs évaluateurs existants, y compris...
Je m'intéresse à divers sujets comme la logique combinatoire, le calcul lambda, la programmation fonctionnelle depuis un certain temps et je les étudie. Cependant, contrairement à la «Théorie du calcul» qui s'efforce de répondre à la question de la «calculabilité», c'est-à-dire des choses qui...
Des combinateurs d'interaction ont été proposés comme cible de compilation pour le λ-calcul auparavant. Cet article met en œuvre le λ-calcul complet. Il est également connu qu'il est possible d' optimiser les codages en réseau d'interaction du λ-calcul pour le sous-ensemble de λ-termes qui est...
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...
Ceci est inspiré par cette question. Soit la collection de tous les combinateurs qui n'ont que deux variables liées. La combinaison C est-elle complète?CC\mathcal{C}CC\mathcal{C} Je pense que la réponse est négative, mais je n'ai pas pu trouver de référence pour cela. Je serais également intéressé...
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....
Dans les rubriques avancées sur les types et les langages de programmation, il est mentionné, dans le chapitre sur les systèmes de types sous-structurels, qu'un calcul lambda affiné "soigneusement conçu" avec un combinateur de récursivité pour les listes ne peut taper que des termes qui ont un...