Przykład, w którym najmniejszy normalny termin lambda nie jest najszybszy

Niech $size$ z $\lambda$ -terms być zdefiniowana w następujący sposób:

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

Niech złożoność terminu \ lambda t będzie zdefiniowana jako liczba równoległych redukcji beta z tx do jego normalnej postaci (przy użyciu optymalnego oceniacza w sensie Levy'ego).$\lambda$$t$$t x$

Szukam przykładu dwóch normalnych $\lambda$ terminów dla tej samej funkcji, w której większy termin ma mniejszą złożoność.

...

Edytuj dla jasności

ponieważ wydaje się, że nie jest oczywiste, o co pytam, postaram się dać dobry przykład. Często istnieje przekonanie, że „naiwna” / „najprostsza” definicja funkcji jest powolna i nieoptymalna. Lepsza wydajność zwiększa złożoność tego terminu, ponieważ potrzebne są dodatkowe struktury danych, formuły itp. Świetnym przykładem jest fibonacci„naiwnie” zdefiniowane jako:

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

Jest to często uważane za „najprostszą” definicję Fib i jest bardzo powolne (wykładnicze). Jeśli rozszerzymy zależności fib( zwykłe definicje dodawania numeru kościoła, pred, is_zero) i znormalizujemy go, otrzymamy ten termin:

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

Ulepszenia, takie jak tabele zapamiętywania, zwiększyłyby ten termin. Jednak istnieje inny termin, który jest znacznie mniejszy ...

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

i, co ciekawe, jest także asymptotycznie lepszy od naiwnego O(N). Ze wszystkich znanych mi definicji jest to zarówno najszybsze, jak i najprostsze . Ten sam efekt dzieje się z sortowaniem. Definicje „naiwne”, takie jak sortowanie bąbelkowe i wstawianie, często są rozszerzane do dużych terminów (ponad 20 linii), ale istnieje mała definicja:

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

Co również bywa szybsze, asymptotycznie, niż każda inna znana mi definicja. Ta obserwacja prowadzi mnie do przekonania, że ​​w przeciwieństwie do powszechnego przekonania, najprostszy termin o najmniejszej złożoności Kołmogorowa jest zwykle szybszy. Moje pytanie jest w zasadzie mokre, czy istnieją jakiekolwiek dowody przeciwne, chociaż ciężko byłoby mi je sformalizować.

$\lambda$

$M$$f(x,y)$$2^y$$P(x)$

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

W konsekwencji:

• $P$

• $P$

• $P$