Eine Lambda-Kalkül-Bewertung mit kirchlichen Ziffern

Ich verstehe, dass eine Kirchenzahl wie aussieht (... n mal ...) $c_n$ $\lambda s. \lambda z. s$ . Dies bedeutet nichts anderesals „die Funktion Applied - mal auf die Funktion “. $s\;z$ $s$ $n$ $z$

Eine mögliche Definition der Funktion ist die folgende: $\mathtt{times}$ . 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: $\mathtt{times} = \lambda m. \lambda n. \lambda s. m \; (n\; s)$

\begin{aligned} (λ m . λ n . λ s . m (n s)) (λ s . λ z . s s z) (λ s . λ z . s s s z) \\ \to^{*} & λ s . (λ s . λ z . s s z) ((λ s . λ z . s s s z) s)) \\ \to^{*} & λ s . (λ s . λ z . s s z) (λ z . s s s z) \\ \to^{*} & λ s . λ z . (λ z . s s s z) (λ z . s s s z) z \end{aligned}

$\begin{align*} (\lambda m. \lambda n. \lambda s. m \; (n\; s))(\lambda s.\lambda z.s\;s\;z)(\lambda s.\lambda z.s\;s\;s\;z) \mspace{-4em} \\ \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; ((\lambda s.\lambda z.s\;s\;s\;z)\; s)) \\ \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; (\lambda z.s\;s\;s\;z) \\ \to^*& \lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z \end{align*}$

Nun, in dieser Situation, wenn ich mich zuerst bewerbe , ich komme zum gewünschten Ergebnis. Wenn ich mich jedoch bewerbe $(\lambda z.s\;s\;s\;z)\;z$ Erstens bekomme ich, wie ich sollte, weil die Anwendung von links assoziativ ist, ein falsches Ergebnis: $(\lambda z.s\;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 \to \lambda s. \lambda z.(s\;s\;s\;(\lambda z.s\;s\;s\;z))\;\;z$

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

lambda-calculus church-numerals codd
quelle

Die Ziffern der Kirche in Ihrer Anfangszeit stimmen nicht. 2 wird durch

, nicht

λ s . λ z . s (s z)

$\lambda s. \lambda z. s (s z)$

λ s . λ z . s s z

$\lambda s. \lambda z. s s z$

Uday Reddy

Antworten:

Ich denke, Ihre Reduzierung ist korrekt (ich habe sie jedoch nur angesehen). Am Ende können Sie nicht auf anwenden , dies erscheint nie im Begriff. ist , nicht . Funktionen in der Lambda-Rechnung nehmen ein einziges Argument an; Sie sind effektiv Curry $(\lambda z. s s s z)$ $z$ $\lambda z. f f z$ $\lambda z. (f f) z$ $\lambda z. f (f z)$ : 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 fachen Zusammensetzung einer Funktion . "Die Funktion wird mal auf die Funktion angewendet " $n$ $n$ $s$ $n$ $z$ . Was Sie geschrieben haben, ist die Funktion die Mal auf die Funktion und schließlich auf angewendet wird, was mir nicht als nützlicher Begriff erscheint. $\lambda s. \lambda z. s (s ( … s \: z) … ))$ $s$ $n-1$ $s$ $z$

ist somit $2 \times 3$ $(\lambda m n s. m (n s)) (\lambda s z. s (s \: z)) (\lambda s z. s (s (s \: z)))$ $\lambda s z. s (s (s (s (s (s \: z)))))$

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