Une évaluation de lambda-calcul impliquant des chiffres Eglise

Question

Je comprends que Église numérique $ c_n $ ressemble $ \ lambda s. \ Lambda z. $ s (... n fois ...) $ s \; z $. Cela signifie rien de plus que « la fonction de $ de $ appliquée $ fois n $ à la fonction $ z $ ».

Une définition possible de la fonction $ $ \ mathtt {} fois est le suivant: $ \ {mathtt fois} = \ lambda m. \ Lambda n. \ Lambda s. m \; (N \; s) $. En regardant le corps, je comprends la logique derrière la fonction. Cependant, quand je commence à évaluer, je suis bloqué. Je vais l'illustrer par un exemple:

$$ \ begin {align *}  (\ Lambda m \ lambda n \ lambda s m \;... (N \; s)) (\ lambda s \ lambda zs \;. S \; z) (\ lambda s \ lambda zs \;. S \ ; s \; z) \ {mspace -4em} \\  \ À ^ * & \ lambda s. (\ Lambda s \ lambda z.s \;. S \; z) \; ((\ Lambda s \ lambda z.s \;. S \, s \, z) \; s)) \\  \ À ^ * & \ lambda s. (\ Lambda s \ lambda z.s \;. S \; z) \; (\ Lambda z.s \; s \; s \; z) \\  \ À ^ * & \ lambda s. \ Lambda z. (\ Lambda z.s \; s \; s \; z) \; (\ lambda z.s \; s \; s \; z) \; z \ End {align *} $$

Dans cette situation, si je suis applique $ (\ lambda z.s \; s \; s \; z) \; z $, je reçois le résultat souhaité. Toutefois, si je demande $ (\ lambda ZS \; s \; s \; z) \; (\ lambda ZS \; s \; s \; z) $ d'abord, comme je parce que l'application est associative de la gauche, Je reçois un mauvais résultat:

$ \ lambda s. \ Lambda z. (\ Lambda z.s \; s \; s \; z) \; (\ lambda z.s \; s \; s \; z) \; z \ to \ lambda s. \ Lambda z. (S \; s \; s \; (\ lambda z.s \; s \; s \; z)) \; \; Z $

Je ne peut plus réduire cela. Qu'est-ce que je fais mal? Le résultat devrait être $ \ lambda s. \ Lambda z.s \; s \; s \; s \; s \; s \; z $

Answer 1

Je pense que votre réduction est correcte (je ne l'ai eyeballed, cependant). A la fin, vous ne pouvez pas appliquer $ (\ lambda z. S s z) $ à $ z $, cela ne figure dans le terme. $ \ Lambda z. f f z $ est $ \ lambda z. (F f) z $, pas $ \ lambda z. f (f z) $. Fonctions du lambda-calcul prennent un seul argument; ils sont efficacement cari : une fonction à deux arguments est mis en oeuvre en fonction d'un argument qui prend le premier argument et retourne un nouvelle fonction à un argument qui prend le second argument et renvoie le résultat.

Vous avez fait la même erreur lors de la définition des chiffres de l'Église. Le chiffre Église pour $ n $ est basé sur la composition d'une fonction $ n $ fois. « La fonction de $ de $ appliquée $ n $ fois à la fonction $ z $ » $ \ lambda s. \ Lambda z. s (s (... s \: z) ...)) $. Qu'est-ce que vous avez écrit est la fonction de $ de $ appliquée n-1 $ fois de $ à la fonction $ de $ et enfin à $ z $, ce qui ne me paraît pas un terme utile.

2 $ \ times 3 $ est donc $ (\ lambda mn s m (ns)). (\ Lambda s z s (s \:. Z)). (\ Lambda s z s (s (s \: z ))) $. Je vous laisse vérifier qu'il ne réduit à $ z de \ lambda. s (s (s (s (s (s: \ z))))). $