教會數字：如何在lambda演算中編碼零？

Question

我學習演算，但我似乎無法理解的編碼數字0

是如何「函數，它在功能和第二個值和應用功能上的說法零次」一零？有沒有其他的方式來編碼零？任何人都可以幫我編碼0嗎？

Answer 1

A「函數，它在功能和第二值，並應用所述函數的自變量的零時刻」，當然，不是零。這是一個編碼爲爲零的。當你處理純粹的lambda演算時，你必須以某種方式對數字（以及其他基本類型）進行編碼，並且對於這些類型中的每一種都有一些要求。例如，對自然數的一個要求是能夠將1加到給定數字上，另一個要能夠將零與較大數字區分開來（如果您想了解更多信息，請查找「Peano算術」）。 Dario引用的流行編碼爲您提供了這兩件事，它也通過N次函數表示一個整數N（編碼爲f參數）N次 - 這是一種使用自然的自然方式。

還有其他可能的編碼 - 例如，一旦您可以表示列表，則可以將N表示爲N個項目的列表。這些編碼有其優點和缺點，但上面的編碼是最受歡迎的編碼。

Answer 2

參見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

如果你學會了演算，你可能已經知道，λxy.yARG1 * ARG2 *將減少ARG2，因爲x被換成什麼，其餘的（λy.y）是身份功能。

你可以用許多其他方式寫出零（即提出一個不同的約定），但是使用λxy.y有很好的理由。例如，你希望零是第一個自然數，所以如果你應用後繼函數，你可以得到1,2,3等等。使用函數λabc.b（abc），可以得到λxy.x（y ），λxy.x（x（y）），λxy.x（x（x（y）））等等，換句話說，你得到一個整數系統。

此外，您希望零是相對於加法的中性元素。與我們的後繼函數S：=λabc.b（ABC），我們可以定義Ñ + * M *爲ñ小號米，即後繼函數來米Ñ倍應用。我們的零λxy.y滿足這個，0 S m和m S 0減小到m。