Eine Lambda Calculus -Bewertung mit kirchlichen Ziffern

Question

Ich verstehe das a Kirchenzahl $ c_n $ sieht aus wie $ lambda s. lambda z. s $ (... n mal ...) $ s ; z $. Dies bedeutet nichts weiter als "Die Funktion $ s $ hat $ n $ mal auf die Funktion $ z $" angewendet.

Eine mögliche Definition der Funktion $ mathtt {Times} $ ist Folgendes: $ mathtt {Times} = lambda m. lambda n. lambda s. m ; (n ; s) $. Wenn ich den Körper betrachte, verstehe ich die Logik hinter der Funktion. Wenn ich jedoch anfange zu bewerten, stecke ich fest. Ich werde es mit einem Beispiel veranschaulichen:

$$ begin {align*} ( lambda m. lambda n. lambda s. m ; (n ; s)) ( lambda s. . lambda zs ; s ; ( lambda s. lambda zs ; s ; z) ; (( lambda s. lambda zs ; s ; s ; z) ; ( lambda s. lambda zs ; s ; z) ; ( lambda zs ; s ; s ; z) bis^*& lambda s. lambda z. ( lambda zs ; s ; s ; z) ; ( lambda zs ;

In dieser Situation, wenn ich zum ersten Mal $ ( lambda zs ; Wenn ich jedoch $ ( lambda zs ; s ; s ; z) ; ( lambda zs ; Ich bekomme ein falsches Ergebnis:

$ lambda s. lambda z. ( lambda zs ; s ; s ; z) ; ( lambda zs ; lambda z. (s ; s ; s ; ( lambda zs ;

Ich kann das nicht mehr reduzieren. Was mache ich falsch? Das Ergebnis sollte $ lambda s sein. lambda zs ; S ; s ; s ; s ; z $

Answer 1

Ich denke, Ihre Reduzierung ist korrekt (ich habe sie jedoch nur ausgesucht). Am Ende können Sie $ ( lambda z. $ lambda z. ffz $ ist $ lambda z. (ff) z $, nicht $ lambda z. F (Fz) $. Funktionen im Lambda-Kalkulus nehmen ein einziges Argument an; Sie sind effektiv Curry: Eine Zwei-Argument-Funktion wird als Ein-Argument-Funktion implementiert, die das erste Argument nimmt und eine neue Ein-Argument-Funktion zurückgibt, die das zweite Argument aufnimmt und das Ergebnis zurückgibt.

Sie haben den gleichen Fehler gemacht, wenn Sie Kirchen Ziffern definieren. Die kirchliche Ziffer für $ N $ basiert darauf, eine Funktion $ n $ mal zu komponieren. "Die Funktion $ s $ hat $ n $ mal auf die Funktion $ z $" $ lambda s angewendet. lambda z. s (s (… s : z)…)) $. Was Sie geschrieben haben, ist die Funktion $ s $ angewendet $ N-1 $ $-mal auf die Funktion $ s $ und schließlich auf $ z $, was mich nicht als nützliche Begriff entspricht.

$ 2 mal 3 $ ist also $ ( lambda mn s. M (ns)) ( lambda s z. S (s : z)) ( lambda s z. S (s : z))) $. Ich werde Sie überprüfen lassen, dass dies auf $ lambda s z reduziert wird. S (s (s (s (s : z)))) $.