8
你怎麼認爲lambda微積分是圖靈完成的事實（以最簡單的方式）？lambda演算的圖靈完備性？
A
回答
8
最直接的方法是在Lambda微積分中實現圖靈機。這很容易，因爲Lambda微積分實際上是一種高級編程語言。這種方法的優點是不需要任何其他的數學依賴關係，因此它應該提供提供論證的最簡單可能的方法。
就數學證明而言，通過實現另一個已經被證明是圖靈完備的範例，最簡單的方法就是μ-遞歸函數。這些已經遞歸定義了，所以它們在Lambda微積分中的表達比圖靈機本身稍微優雅。
1
Brainfuck是非常密切的模型圖靈機， 你會發現在 http://en.wikipedia.org/wiki/Binary_lambda_calculus#Brainfuck
相關問題
- 1. 圖靈的完備性
- 2. 質疑LAMBDA演算
- 3. lambda演算中的量詞
- 4. 修改後的Brainfuck版本的圖靈完備性
- 5. 基於constexpr的計算圖靈完整？
- 6. 算法的健全性和完備性
- 7. 在lambda表達式中表演性能
- 8. 在理解計算中，我無法理解這個lambda演算
- 9. VHDL圖靈是否完整？
- 10. 批次圖靈完成嗎？
- 11. 計算理論圖靈機
- 12. 帶輸出問題的Lambda演算解釋器
- 13. Lisp鬆散地是什麼類型的lambda演算？
- 14. 在代表中演示lambda
- 15. 我的程序是否完成圖靈？
- 16. 尋找非圖靈完成的語言
- 17. 教會數字：如何在lambda演算中編碼零？
- 18. Actionscript3是否提供列表解析或lambda演算？
- 19. 如何在球拍中應用lambda演算規則？
- 20. 非確定性圖靈機
- 21. 圖像精靈和觸摸設備
- 22. 關於UML和圖靈完全
- 23. 是SQL甚至TSQL圖靈完成？
- 24. lambda的模板參數演繹
- 25. 從lambda的模板參數演繹
- 26. 計算反演？
- 27. 命題演算
- 28. 斯卡拉的類型系統的哪個屬性使它完成圖靈？
- 29. 平方根計算圖靈機
- 30. 關於神經網絡的圖靈完備性有哪些實用的證明？什麼nns可以執行代碼/算法？
闡述了一個演算解釋你展示語言，所有的[μ-遞歸函數（HTTPS：//en.wikipedia .org/wiki /％CE％9C-recursive_function）可以在lambda演算中表示，然後依賴於那些圖靈完備性結果 – 2012-03-08 14:31:34