3
$\begingroup$

Well-known example of divergent expression in lambda calculus is big-Omega combinator, defined as (λf. f f)(λf. f f). Although big-Omega is divergent expression, it's size became stable and always equal (λf. f f)(λf. f f) . Big-Omega combinator can be extended to provide more growth speed, for instance, expression (λf. f f f)(λf. f f f) has linear growth speed and increases by one term (λf. f f f) via one beta-reduction.

Expression divergence growth speed can be significantly increased to exponential one with using following lambda-expression (λf.λu. f f (u u))(λf.λu. f f (u u))(λx.x), which doubles (λx.x) every two beta-reductions. Of course, by doubling (u u) in (λf.λu. f f (u u)) term growth speed can be increased, but still left in exponential class. Also, another mechanics can be applied to increase growth so on.

But question is: which lambda expression has largest theoretically-known growth speed, and what this growth speed is? For example, in different mathematical fields there are huge numbers, like Tree(3) or BigFoot. Maybe is there known something like equivalent for lambda-calculus - divergent expression with maximum divergence growth speed?

Thanks!

$\endgroup$
2
  • 1
    $\begingroup$ Obviously, there is no function with the largest growth speed, since you could always take it and (say) double it. A reasonable question though, is "what growth speeds are possible"? $\endgroup$
    – cody
    Commented Oct 10, 2023 at 19:43
  • $\begingroup$ @cody Of course you are right, and thank you for the question correction! I meant something like growth asymptotic, independent on constants. In that case doubling growth speed still stays in class exp(c*l), where l is expression length variable and c is arbitrary constant, which cat be unbounded large. Thanks! $\endgroup$ Commented Oct 11, 2023 at 8:56

1 Answer 1

2
$\begingroup$

Ok, I want to interpret this question as: what is the biggest growth rate a term $t$ of size $|t| = C$ can have, after $n$ $\beta$-reductions (as a function of $n$).

There are several different interpretations for the question, as well as within the question: for example, am I allowed to pick which $\beta$-reduction I want at each step, or do I want the "worst case" (smallest increase possible)?

All these questions are interesting!

It's pretty easy to bound the growth from above by $C^{2^n}$ (double exponential): a redex $(\lambda x.t)\ u$ has at most $C$ occurrences of $x$ and the size of $u$ is also bounded by $C$, which gives $C^2$ as the maximum size for $t[u/x]$.

Iterating this gives $(({C^2})^2)^\ldots$, that is, $C^{2^n}$.

But is this upper bound attained? I suspect not. As you note, there is an exponential lower bound, which leaves quite a gap.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.