patternMinor
Expression with fastest growth in lambda-calculus
Viewed 0 times
expressioncalculuswithfastestgrowthlambda
Problem
Well-known example of divergent expression in lambda calculus is big-Omega combinator, defined as
Expression divergence growth speed can be significantly increased to exponential one with using following lambda-expression
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!
(λ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!
Solution
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.
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.
Context
StackExchange Computer Science Q#162385, answer score: 2
Revisions (0)
No revisions yet.