开发者

Query on Lambda calculus

Continuing on exercises in book Lambda Calculus, the question is as follows:

Suppose a symbol of the λ-calculus alphabet is always 0.5cm wide. Write down a λ-term with length less than 20 cm having a normal form with length at least (10^开发者_JAVA技巧10)^10 lightyear. The speed of light is c = 3 * (10^10) cm/sec.

I have absolutely no idea as to what needs to be done in this question. Can anyone please give me some pointers to help understand the question and what needs to be done here? Please do not solve or mention the final answer.

Hoping for a reply.

Regards, darkie


Not knowing anything about lambda calculus, I understand the question as following:

You have to write a λ-term in less than 20 cm, where a symbol is 0.5cm, meaning you are allowed less than 40 symbols. This λ-term should expand to a normal form with the length of at least (10^10)^10 = 10^100 lightyears, which results in (10^100)*2*3*(10^10)*24*60*60 symbols. Basically a very long recursive function.


Here's another hint: in lambda calculus, the typical way to represent an integer is by its Church encoding, which is a unary representation. So if you convert the distances into numbers, one thing that would do the trick would be a small function which, when applied to a small number, terminates and produces a very large number.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜