Kirche Ziffern: wie Null in Lambda-Kalkül codieren?

Question

ich Lambda-Kalkül lerne, aber ich kann die Codierung für die Zahl 0 zu verstehen scheinen.

Wie ist „ Funktion, die in einer Funktion und einem zweiten Wert annimmt, und wendet die Funktion Null-mal auf dem Argument “ eine Null? Gibt es eine andere Art und Weise null zu kodieren? Kann mir jemand hier helfen 0 kodieren?

Answer 1

A „Funktion, die in einer Funktion und einem zweiten Wert annimmt, und wendet die Funktion Null mal auf das Argument“ ist natürlich nicht Null. Es ist eine Codierung von Null. Wenn Sie mit einfachen Lambda-Kalkül beschäftigen, müssen Sie Zahlen kodieren (wie auch andere primitive Typen) in irgendeiner Weise, und es gibt ein paar Anforderungen für jeden dieser Typen diktiert. Zum Beispiel ist eine Voraussetzung für die natürlichen Zahlen der Lage sein, eine bestimmte Anzahl hinzuzufügen 1, und ein anderer ist, um von größeren Zahlen zu unterscheiden Null (wenn Sie mehr wissen möchten, suchen Sie nach „Peano Arithmetik“). Die beliebte Codierung, die Dario zitierte gibt Ihnen diese beiden Dinge, und es repräsentiert auch eine ganze Zahl N durch eine Funktion, die etwas (codiert als f Argument) hat N-mal -., Die eine Art natürliche Weise ist Naturals zu verwenden

Es gibt auch andere Codierungen, die möglich sind - zum Beispiel, wenn Sie Listen darstellen können, können Sie N als eine Liste von N Elementen darstellen. Diese Kodierungen haben ihre Vor- und Nachteile, aber die oben ist bei weitem der beliebteste.

Answer 2

Siehe wikipedia :

0 ≡ λf.λx. x
1 ≡ λf.λx. f x
2 ≡ λf.λx. f (f x)
3 ≡ λf.λx. f (f (f x))
...
n ≡ λf.λx. fn x

Answer 3

Wenn Sie Lambda-Kalkül lernen, werden Sie wahrscheinlich bereits wissen, dass λxy.y arg1 * arg2 * reduziert auf arg2 , da die x durch nichts ersetzt wird, und die Rest (λy.y) ist die Identitätsfunktion.

Sie könnten Null auf viele andere Weisen schreiben (das heißt mit einer anderen Konvention kommen), aber es gibt gute Gründe für die Verwendung λxy.y. Zum Beispiel möchten Sie Null, um die erste natürliche Zahl ist, so dass, wenn Sie die Nachfolgerfunktion für sie gelten, Sie erhalten 1, 2, 3 usw. Mit der Funktion λabc.b (abc), Sie λxy.x (y erhalten ), λxy.x (x (y)), λxy.x (x (x (y))) usw., mit anderen Worten, Sie erhalten ein ganzes Zahlensystem.

Darüber hinaus wollen Sie Null das neutrale Element sein bezüglich der Addition. Mit unserer Nachfolgerfunktion S: = λabc.b (abc), können wir definieren n + * m * als n S m , das heißt, n mal die Anwendung der Nachfolgerfunktion auf m . Unsere Null λxy.y erfüllt diese, die beide 0 S m und m S 0 reduzieren m .