質疑LAMBDA演算

繼續在書中Lambda Calculus練習，問題如下：質疑LAMBDA演算

假設λ演算的象徵字母總是0.5釐米寬。寫下向下長度小於20的λ-項 cm具有正常形式，長度至少爲（10^10）^ 10光年的。光速爲 c = 3 *（10^10）cm/sec。

我完全不知道這個問題需要做什麼。任何人都可以請給我一些指針幫助理解問題和需要在這裏做什麼？請不要解決或提到最終答案。

希望得到答覆。

問候， darkie

來源

2010-06-21 name_masked

我認爲這是一個有效的問題，因爲lambda演算現在變得越來越重要。 – 2010-06-21 00:36:17

不知道有關演算什麼，我明白的問題如下：

你必須寫在不到20釐米的λ-項，其中符號是0.5釐米，這意味着您可以少於40個符號。這個λ-項應該擴展到至少（10^10）^ 10 = 10^100光年的正常形式，其導致（10^100）* 2 * 3 *（10^10）* 24 * 60 * 60個符號。基本上是一個很長的遞歸函數。

來源

2010-06-21 00:23:44 Femaref

我認爲您的分析工作做得很好，並且您已經足夠容易地編寫解決方案。 – 2010-06-21 00:38:08

我有一個疑問，我怎麼能確定我的λ遞歸函數會超過那麼多符號？我的意思是，這是太多的符號來確保，不是嗎？ – 2010-06-21 00:40:46

是的，測試太多了 - 這正是任務的重點。您需要定義一個功能，其速度非常快。這種功能的一個例子是[阿克曼功能]（http://en.wikipedia.org/wiki/Ackermann_function）。我不確定這在λ-演算中有多遠。忙碌的海狸也是這樣的一個功能，在所有範圍內增長得非常快。 – Femaref 2010-06-21 00:57:31

這是另一個提示：在lambda微積分中，表示整數的典型方法是通過其Church編碼，這是一個一元表示。所以如果你將距離轉化爲數字，那麼一件事就是做一個小函數，這個小函數應用於一個小數字時會終止併產生一個非常大的數字。

來源

2010-06-21 16:46:06

質疑LAMBDA演算

回答

相關問題