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 będzie zdefiniowana jako liczba równoległych redukcji beta z 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ć.

— MaiaVictor
źródło

Nie

ma złożoność sqrt (n).

n! = n . n - 1....2.1

$n!=n.n-1....2.1$

— T ....

Jestem prawie pewien, że możesz zakodować podział próbny za pomocą krótszego

-term niż algorytm AKS.

λ

$\lambda$

— Emil Jeřábek

Zgadzam się z @ EmilJeřábek i tak naprawdę nie widzę, jak nie można uzyskać przykładu, patrząc na algorytmy sortowania, tak jak już to zrobiliście: czy

-term implementujący sortowanie bąbelkowe nie jest krótszy niż implantacja

, powiedzmy , sortuj stos? Lub, nie wiem, wyszukiwanie metodą brute force, super krótkie do wdrożenia, ale wykładnicze, w porównaniu do sprytnego algorytmu czasu policyjnego wymagającego więcej linii kodu ...? Muszę coś przeoczyć, obawiam się, że tak naprawdę nie rozumiem pytania.

λ

$\lambda$

λ

$\lambda$

— Damiano Mazza

Nie podjąłem żadnego wysiłku, aby to zapisać, ale jako zasada heurystyczna wybór języka programowania zwykle nie wpływa na względne długości dwóch algorytmów i nie widzę absolutnie żadnego powodu, dla którego

rachunek powinien być wyjątkiem. Zwróć uwagę w szczególności, że normalizacja to tutaj czerwony śledź: najbardziej naturalny sposób wyrażania algorytmów w

rachunku daje normalne warunki od samego początku, a w każdym razie, IIRC z mojego doświadczenia z Unlambda, możesz przekształcić dowolny termin w normalny termin o podobnej długości dający ten sam wynik po zastosowaniu.

λ

$\lambda$

λ

$\lambda$

— Emil Jeřábek

I tak, jak wspomina Damiano, AKS był tylko przykładem. To samo powinno dotyczyć mniej więcej każdej sytuacji, w której mamy trywialny nieefektywny algorytm i wydajne, ale o wiele bardziej wyrafinowane rozwiązanie tego samego problemu.

— Emil Jeřábek

$\lambda$

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

$\lambda$ $g$ $P$ $h$ $P$ $f$ $g$
$fa (x, M. (h, x)) \leq M. (sol, x) dla wszystkich wystarczająco dużych wejść x,$ $f(x,M(h,x))\le M(g,x)\text{ for all large enough inputs }x,$

$M(g,x)$ $g$ $x$ $M$

W konsekwencji:

— Emil Jeřábek
źródło