质疑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演算

回答

相关问题