Eine Lambda-Kalkül-Bewertung mit kirchlichen Ziffern

10

Ich verstehe, dass eine Kirchenzahl wie λ s aussieht . λ z . s (... n mal ...) scnλs.λz.s . Dies bedeutet nichts anderesals „die Funktion s Applied n - mal auf die Funktion z “.szsnz

Eine mögliche Definition der Funktion ist die folgende: t i m e s = λ m . λ n . λ s . mtimes . Wenn ich den Körper betrachte, verstehe ich die Logik hinter der Funktion. Wenn ich jedoch mit der Bewertung beginne, stecke ich fest. Ich werde es anhand eines Beispiels veranschaulichen:times=λm.λn.λs.m(ns)

(λm.λn.λs.m(ns))(λs.λz.ssz)(λs.λz.sssz)λs.(λs.λz.ssz)((λs.λz.sssz)s))λs.(λs.λz.ssz)(λz.sssz)λs.λz.(λz.sssz)(λz.sssz)z

Nun, in dieser Situation, wenn ich mich zuerst bewerbe , ich komme zum gewünschten Ergebnis. Wenn ich mich jedoch bewerbe ( λ z . S.(λz.sssz)z Erstens bekomme ich, wie ich sollte, weil die Anwendung von links assoziativ ist, ein falsches Ergebnis:(λz.sssz)(λz.sssz)

λs.λz.(λz.sssz)(λz.sssz)zλs.λz.(sss(λz.sssz))z

Ich kann das nicht mehr reduzieren. Was mache ich falsch? Das Ergebnis sollte λs.λz.ssssssz

codd
quelle
Die Ziffern der Kirche in Ihrer Anfangszeit stimmen nicht. 2 wird durch , nicht λ s . λ z . s s z . λs.λz.s(sz)λs.λz.ssz
Uday Reddy

Antworten:

7

Ich denke, Ihre Reduzierung ist korrekt (ich habe sie jedoch nur angesehen). Am Ende können Sie nicht auf z anwenden , dies erscheint nie im Begriff. λ z . f f z ist λ z . ( f f ) z , nicht λ z . f ( f z ) . Funktionen in der Lambda-Rechnung nehmen ein einziges Argument an; Sie sind effektiv Curry(λz.sssz)zλz.ffzλz.(ff)zλz.f(fz): Eine Funktion mit zwei Argumenten wird als Funktion mit einem Argument implementiert, die das erste Argument verwendet und eine neue Funktion mit einem Argument zurückgibt, die das zweite Argument verwendet und das Ergebnis zurückgibt.

Sie haben den gleichen Fehler gemacht, als Sie die Ziffern der Kirche definiert haben. Die Kirchenzahl für basiert auf der n- fachen Zusammensetzung einer Funktion . "Die Funktion s wird n- mal auf die Funktion z angewendet " λ s . λ z . s ( s ( snnsnz . Was Sie geschrieben haben, ist die Funktion s, die n - 1 Mal auf die Funktion s und schließlich auf z angewendet wird, was mir nicht als nützlicher Begriff erscheint.λs.λz.s(s(sz)))sn1sz

ist somit ( λ m n s . M ( n s ) ) ( λ s z . S ( s2×3(λmns.m(ns))(λsz.s(sz))(λsz.s(s(sz)))λsz.s(s(s(s(s(sz)))))

Gilles 'SO - hör auf böse zu sein'
quelle
Was Ihren Absatz betrifft, haben Sie Recht, und mir war dies bewusst. Es ist mir nur aufgefallen, dass die richtige Assoziativierung das richtige Ergebnis erbracht hat. Zum zweiten Absatz: Sie haben Recht. Die Verwendung von geschweiften Klammern war für mich falsch, wiederum wegen der linken Assoziativität der Anwendung. Ich werde das Ganze jetzt noch einmal reduzieren und sehen, ob mein Mangel an Zahnspangen meinen Fehler verursacht hat!
Codd
Es tat es. Sie haben festgestellt, dass meine Notation eine falsche Reihenfolge der Anwendung impliziert und das Problem gelöst hat! Akzeptiere deine Antwort.
Codd