There are some terms in lambda calculus that don't really have a normal term. My question is for a term like the following:

$$T \overset{def}{=} \lambda f. (\lambda x. \; f \; (f \; (f \; x)))$$

$T$ takes a function as its argument and transforms the function space by applying it three times. If I apply $T$ to itself, I will be initially left with $$\lambda f. (\lambda x. \; f \; (f \; (f \; x)))\; \lambda f. (\lambda x. \; f \; (f \; (f \; x)))\; \lambda f. (\lambda x. \; f \; (f \; (f \; x)))$$

But I can continue to do this an infinite amount of times. After my first reduction, I am left with 3 terms. So how do we define the growth of the function per reduction? Do we say that my next reduction will leave me with 9 terms, or 27? Or 81?

Also, how do we define the nature of the expression? Does it have a normal form?

  • 2
    $\begingroup$ Your term sure looks like the church numeral 3 (en.wikipedia.org/wiki/Church_encoding#Church_numerals). Surprisingly, applying this numeral to itself reduces to a church numeral which is a) a normal form, b) exactly the numeral $3^3$, so $27$... $\endgroup$ – cody May 12 '17 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.