Пример, где наименьший нормальный лямбда-член не самый быстрый

Пусть о Л -терминов быть определены следующим образом :$size$$\lambda$

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

Пусть сложность -term определяется как число параллельных бета-сокращений от до его нормальной формы (с использованием оптимального оценщика в смысле Леви).$\lambda$$t$$t x$

Я ищу пример двух нормальных -термов для одной и той же функции, где больший член имеет меньшую сложность.$\lambda$

...

Изменить для ясности

так как кажется, что неясно, о чем я спрашиваю, я попытаюсь привести убедительный пример. Часто существует мнение, что «наивное» / «простейшее» определение функции является медленным и неоптимальным. Повышение производительности повышает сложность этого термина, поскольку вам нужны дополнительные структуры данных, формулы и т. Д. Отличный пример fibonacci, который можно «наивно» определить как:

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

Это часто рассматривается как «самое простое» определение fib, и оно очень медленное (экспоненциальное). Если мы расширим зависимости fib( обычные определения для добавления номера церкви, pred, is_zero) и нормализуем его, мы получим этот термин:

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

Усовершенствования, такие как таблицы памятки, сделают этот термин больше. Тем не менее, существует другой термин, который гораздо меньше ...

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

и, что любопытно, также асимптотически превосходит наивного, вбегающего O(N). Из всех определений, которые я знаю, это и самый быстрый и самый простой . Тот же эффект происходит с сортировкой. «Наивные» определения, такие как пузырьковая сортировка и вставка, часто расширяются до огромных терминов (более 20 строк), но существует небольшое определение:

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

Что также оказывается быстрее, асимптотически, чем любое другое определение, которое я знаю. Это наблюдение заставляет меня полагать, что, в отличие от распространенного мнения, самый простой термин с наименьшей колмогоровской сложностью обычно быстрее. Мой вопрос в основном более влажен, есть какие-то доказательства обратного, хотя мне было бы трудно его формализовать.

Теорема Блюма об ускорении обычно формулируется на языке частично рекурсивных функций, но вплоть до тривиальных различий в нотации она работает точно так же на языке -calculus.$\lambda$

Это говорит о том, что при любой разумной мере сложности (например, оптимальное число сокращений, как в вопросе) и рекурсивной функции (например, ), мы можем найти рекурсивный предикат такой, что:$M$$f(x,y)$$2^y$$P(x)$

Для каждого алгоритма (т. Е. -term в нормальной форме здесь) вычисляющего , существует другой алгоритм для который имеет -скорость над : $\lambda$$g$$P$$h$$P$$f$$g$

$$f(x,M(h,x))\le M(g,x)\text{ for all large enough inputs }x,$$

где обозначает сложность вычисления на входе в соответствии измерения .$M(g,x)$$g$$x$$M$

Следовательно:

• $P$ не имеет асимптотически оптимального алгоритма в данной мере

• в частности, кратчайший алгоритм для не асимптотически оптимален$P$

• для любого алгоритма для существует асимптотически более быстрый алгоритм, нормальная форма которого длиннее (поскольку до переименования переменных существует только конечное число нормальных членов заданной длины)$P$