Évaluation du calcul lambda

8

Je sais que c'est une question simple mais quelqu'un peut-il me montrer comment (λy.λx.λy.y)(λx.λy.y) réduit à λx.λy.y.

prerm2686
la source
Êtes-vous sûr d'avoir correctement mis les parenthèses? Parce que la façon dont il est écrit, je ne vois pas du tout comment le simplifier. Si c'était le cas (λy.λx.λy.y) (λx.λy.y), cela se réduirait à λx.λy.y.
sepp2k
Oui merci j'ai mis à jour ma question. Pourriez-vous expliquer comment vous avez obtenu λx.λy.y
prerm2686

Réponses:

10

La raison pour laquelle (λy.λx.λy.y)(λx.λy.y) réduit à λx.λy.y et non λx.λy.λx.λy.y est-ce le y dans le corps de λy.λx.λy.y fait référence à l'argument du troisième lambda, et non au premier.

Si vous renommez les arguments pour qu'ils aient des noms distincts, λy.λx.λy.y serait écrit comme λy1.λx.λy2.y2. Donc, si vous appliquez cette fonction à l'argument, cela signifie que chaque occurrence dey1 dans λx.λy2.y2devrait être remplacé par l'argument. toutefoisy1 n'apparaît pas du tout dans cette expression, donc l'argument est simplement ignoré et le résultat est juste λx.λy2.y2.

sepp2k
la source
Oh ok donc le y2 n'est pas lié à y1. Merci beaucoup.
prerm2686
7
@ prerm2686 Une variable est toujours liée par l'enveloppe la plus proche λ. Le sous-termeλy.y est la fonction d'identité, peu importe où vous l'utilisez, même si vous l'utilisez dans un contexte qui utilise également le nom de la variable y.
Gilles 'SO- arrête d'être méchant'
La réduction sur wikipedia donne un traitement plus formel de la conversion α et de la réduction β. Une référence que j'aime est le livre de Chris Hankin
Romuald