Query on Lambda calculus

Question

Hi All,

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^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

Answer 1

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.

Answer 2

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.