11
$\begingroup$

Let the $size$ of $\lambda$-terms be defined as follows:

  • $size(x) = 1$,
  • $size(λx.t) = size(t) + 1$,
  • $size(t s) = size(t) + size(s) + 1$.

Let the complexity of a $\lambda$-term $t$ be defined as the number of parallel beta reductions from $t x$ to its normal form (using an optimal evaluator in Levy's sense).

I am looking for an example of two normal $\lambda$-terms for the same function where the larger term has lower complexity.

...

Edit for clarity

since it seems that it is not obvious what I'm asking, I'll try to give a solid example. There is often a belief that the "naive"/"simplest" definition of a function is slow and not optimal. Better performance increase the complexity of the term, since you need added data-structures, formulas, etc. A great example is fibonacci, which can be "naively" defined as:

-- The fixed fibonacci definition
fib_rec fib n =
    if (is_zero x) 
        then 1 
        else fib (n - 1) + f (n - 2)

-- Using church numbers instead of the λ-combinator to get a normal form
fib n = n fib_rec 0 n 

This is often regarded as the "simplest" definition of fib, and is very slow (exponential). If we expand the dependencies of fib (the usual definitions for church-number addition, pred, is_zero), and normalize it, we get this term:

fib = (λa.(a(λbc.(c(λdef.f)(λde.d)(λde.(de))
      (λde.(b(λfg.(c(λhi.(i(hf)))(λh.g)(λh.h)))
      d(b(λfg.(c(λhi.(i(h(λjk.(k(jf))))))(λhi.g)
      (λh.h)(λh.h)))de)))))(λbc.c)a))

Improvements such as memoization tables would make this term bigger. Yet, there exists a different term that is much smaller...

fib = (λa.(a(λb.(b(λcde.(e(λfg.(cf(dfg)))c))))
      (λb.(b(λcd.(cd))(λcd.d)))(λbc.b)))

and, curiously, is also asymptotically superior to the naive one, running in O(N). Of all definitions I'm aware, this is both the fastest and the simplest. The same effect happens with sort. "Naive" definitions such as bubble sort and insertion sort often get expanded to huge terms (20+ lines long), but there exists a small definition:

-- sorts a church list (represented as the fold) of church numbers
sort = λabc.a(λdefg.f(d(λhij.j(λkl.k(λmn.mhi)l)(h(λkl.l)i))
       (λhi.i(λjk.bd(jhk))(bd(h(λjk.j(λlm.m)k)c))))e)(λde.e)
       (λde.d(λfg.g)e)c

Which also happens to be faster, asymptotically, than every other definition I know. This observation leads me to believe that, as opposed to common belief, the simplest term, with smallest Kolmogorov complexity, is usually the faster. My question is basically wether there is any evidence of the opposite, although I'd have a hard time in formalizing it.

$\endgroup$
  • 3
    $\begingroup$ No $n!=n.n-1....2.1$ has sqrt(n) complexity. $\endgroup$ – T.... Aug 23 '15 at 4:46
  • 2
    $\begingroup$ I’m pretty sure you can code trial division by a shorter $\lambda$-term than the AKS algorithm. $\endgroup$ – Emil Jeřábek Aug 24 '15 at 14:41
  • 2
    $\begingroup$ I agree with @EmilJeřábek and, actually, I don't see how an example is not obtained by looking at sorting algorithms, as you already did: isn't the $\lambda$-term implementing bubble sort shorter than the $\lambda$-term implmenting, say, heap sort? Or, I don't know, a brute-force search, super short to implement but exponential time, vs. a clever polytime algorithm requiring more lines of code...? I must be missing something, I am afraid I don't really understand the question. $\endgroup$ – Damiano Mazza Aug 24 '15 at 15:33
  • 1
    $\begingroup$ I made no effort to actually write it down, but as a heuristic principle, the relative lengths of two algorithms are usually not affected very much by the choice of the programming language, and I see absolutely no reason $\lambda$-calculus should be an exception. Note in particular that normalization is a red herring here: the most natural way how to express algorithms in $\lambda$-calculus gives normal terms from the get-go, and anyway, IIRC from my experience with Unlambda, you can transform any term into a normal term of similar length giving the same result when applied. $\endgroup$ – Emil Jeřábek Aug 24 '15 at 16:12
  • 2
    $\begingroup$ And yes, as Damiano mentions, AKS was just an example. The same should hold in more or less any situation where we have a trivial inefficient algorithm, and an efficient but much more sophisticated solution of the same problem. $\endgroup$ – Emil Jeřábek Aug 24 '15 at 16:23
10
$\begingroup$

Blum’s speedup theorem is usually stated in the language of partially recursive functions, but up to trivial differences in notation, it works just the same in the language of $\lambda$-calculus.

It says that given any reasonable complexity measure $M$ (for example, the optimal number of reductions as in the question) and a recursive function $f(x,y)$ (for example, $2^y$), we can find a recursive predicate $P(x)$ such that:

For every algorithm (i.e., $\lambda$-term in normal form here) $g$ computing $P$, there is another algorithm $h$ for $P$ that has $f$-speedup over $g$: $$f(x,M(h,x))\le M(g,x)\text{ for all large enough inputs }x,$$

where $M(g,x)$ denotes the complexity of the computation of $g$ on input $x$ according to measure $M$.

Consequently:

  • $P$ has no asymptotically optimal algorithm in the given measure

  • in particular, the shortest algorithm for $P$ is not asymptotically optimal

  • for any algorithm for $P$, there is an asymptotically faster algorithm whose normal form is longer (because up to renaming of variables, there are only finitely many normal terms of a given length)

$\endgroup$

Your Answer

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

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