怎麼理解邱奇計數？

1樓：劉子超

剛看到sicp這道題，說一下我的看法，不對請指正。

這裡用數學符號再寫一遍就很直觀了

zero=λf.λx.x

one =λf.λx.f(x)

two =λf.λx.f(f(x))

add1(n)=λf.λx.f((n(f))(x))add1(zero)=λf.

λx.f(x)等同於oneadd1(one) =λf.λx.

f(f(x))等同於two所以丘奇計數n說的是讓你傳乙個函式f和乙個引數x，f對x作用n次另外不管是zero，one，two中

λf.λx等同於λfx，前者就是後者柯里化的結果，用後者表示前者也不影響結果

2樓：王見充

它是通過指定函式引數呼叫次數的方式來記錄自然數從 1 開始比較好理解：

用 g(1)(f)(x) = f(x) 來記錄 1用 g(2)(f)(x) = f(f(x)) = f^2(x) 來記錄 2

用 g(3)(f)(x) = f(f(f(x))) = f^3(x) 來記錄 3

依次類推

倒推可得 g(0)(f)(x) = x

省略兩邊f的引數就是：

用 g(1)(f) = f 來記錄 1

用 g(2)(f) = f^2 來記錄 2用 g(3)(f) = f^3 來記錄 3省略其本身的引數 f 來表述就是：

用 g(1) 的結果函式來記錄 1 這個數字用 g(2) 的結果函式來記錄 2 這個數字用 g(3) 的結果函式來記錄 3 這個數字所以說，它的實質就是通過記錄 lambda f = f^n 這樣的函式來記錄自然數的

3樓：

就是帶括號的扳手指數數

扳手指的時候

1 表示1

11 表示 2

111 表示 3

現在Church說了，數數也要用括號

(1 ()) 表示 1

(1 (1 ())) 表示 2

(1 (1 (1 ()))) 表示 3

以上不完全準確，大意就是這樣

4樓：「已登出」

Programming with Nothing ruby 版本的。。

只用函式 -> p // 這樣得完成了 FizzBuzz 題目。。

5樓：戴為

邱奇的λ演算理論是乙個高度形式化的理論。他定義了一種符號運算規則，叫做λ表示式（依我的理解，這種規則似乎以替換為核心）。姑且把這種符號所代表的元素稱為「函式」，這些函式作用的物件和給出的結果是與它自身同一型別的元素，也就是說，也是函式。

（其實我個人更傾向於將之理解為一種代數結構，把「作用於」這個行為理解為乙個二元運算。但這種理解方式似乎不是主流。）

λ表示式是對這些符號的乙個抽象運算。具體規則我一兩句話說不清楚。

在λ表示式的規則下，用題中這種方法定義的一族元素（乙個用於描述乙個函式迭代多少次的函式），恰好具有和用皮亞諾公理定義的「自然數」完全相同的性質，因此我們不妨也稱之為自然數。

這就是邱奇計數和皮亞諾公理的關係了。

至於邱奇圖靈議題，是基於這套理論的另乙個結論（稱之為「議題」或許更好些）。邱奇聲稱，任何「可計算」的運算，都可以寫成乙個λ表示式。後來這被證明和圖靈機假設是等價的。

也就是說，邱奇圖靈議題可以被認為是對「可計算性」的乙個定義：任何乙個可以被圖靈機實現的運算一定可以寫成乙個λ表示式，反之亦然，我們稱這樣的運算是可計算的。

總之，邱奇的λ演算理論是邱奇計數和邱奇圖靈議題的出發點。它們的關係就是這樣了。