Contoh di mana istilah lambda normal terkecil tidak tercepat

Biarkan $size$ dari $\lambda$ -terms didefinisikan sebagai berikut:

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

Biarkan kompleksitas -term didefinisikan sebagai jumlah reduksi beta paralel dari ke bentuk normalnya (menggunakan evaluator optimal dalam pengertian Levy). $\lambda$ $t$ $t x$

Saya mencari contoh dua normal- -terms untuk fungsi yang sama di mana istilah yang lebih besar memiliki kompleksitas yang lebih rendah. $\lambda$

...

Edit untuk kejelasan

karena tampaknya tidak jelas apa yang saya minta, saya akan mencoba memberikan contoh yang solid. Seringkali ada kepercayaan bahwa definisi "naif" / "paling sederhana" dari suatu fungsi adalah lambat dan tidak optimal. Kinerja yang lebih baik meningkatkan kompleksitas istilah, karena Anda perlu menambahkan struktur data, formula, dll. Contoh yang bagus adalah fibonacci, yang dapat "naif" didefinisikan sebagai:

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

Ini sering dianggap sebagai definisi "paling sederhana" dari fib, dan sangat lambat (eksponensial). Jika kita memperluas dependensi fib( definisi yang biasa untuk penambahan nomor gereja, pred, is_zero), dan menormalkannya, kita mendapatkan istilah ini:

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

Perbaikan seperti tabel memoisasi akan membuat istilah ini lebih besar. Namun, ada istilah berbeda yang jauh lebih kecil ...

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

dan, anehnya, juga asimtotik unggul satu naif, berjalan di O(N). Dari semua definisi yang saya ketahui, ini adalah yang tercepat dan paling sederhana . Efek yang sama terjadi dengan sort. Definisi "Naif" seperti jenis gelembung dan jenis sisipan sering diperluas menjadi istilah besar (panjang 20+ baris), tetapi ada definisi kecil:

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

Yang juga terjadi lebih cepat, tanpa gejala, dari setiap definisi lain yang saya tahu. Pengamatan ini membuat saya percaya bahwa, berbeda dengan kepercayaan umum, istilah paling sederhana, dengan kompleksitas Kolmogorov terkecil, biasanya lebih cepat. Pertanyaan saya pada dasarnya adalah apakah ada bukti yang berlawanan, walaupun saya mengalami kesulitan dalam memformalkannya.

lo.logic computability pl.programming-languages lambda-calculus Viktor Maia
sumber

No memiliki kompleksitas sqrt (n).

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

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

T ....

Saya cukup yakin Anda dapat membuat kode divisi percobaan dengan -term yang lebih pendek daripada algoritma AKS.

λ

$\lambda$

Emil Jeřábek

Saya setuju dengan @ EmilJeřábek dan, sebenarnya, saya tidak melihat bagaimana contoh tidak diperoleh dengan melihat algoritma pengurutan, seperti yang sudah Anda lakukan: bukan -term yang mengimplementasikan bubble sort lebih pendek daripada implementasi -term , katakanlah, tumpukan semacam? Atau, saya tidak tahu, pencarian brute-force, super singkat untuk diimplementasikan tetapi waktu eksponensial, vs algoritma polytime pintar yang membutuhkan lebih banyak baris kode ...? Saya pasti kehilangan sesuatu, saya khawatir saya tidak benar-benar mengerti pertanyaan itu.

λ

$\lambda$

λ

$\lambda$

Damiano Mazza

Saya tidak berusaha untuk benar-benar menuliskannya, tetapi sebagai prinsip heuristik, panjang relatif dari dua algoritma biasanya tidak terlalu terpengaruh oleh pilihan bahasa pemrograman, dan saya benar-benar tidak melihat alasan -calculus harus menjadi pengecualian. . Perhatikan khususnya bahwa normalisasi adalah herring merah di sini: cara paling alami bagaimana mengekspresikan algoritme di -calculus memberikan istilah normal sejak awal, dan lagi pula, IIRC dari pengalaman saya dengan Unlambda, Anda dapat mengubah istilah apa pun menjadi istilah normal dengan panjang yang sama memberikan hasil yang sama ketika diterapkan.

λ

$\lambda$

λ

$\lambda$

Emil Jeřábek

Dan ya, seperti yang disebutkan Damiano, AKS hanyalah sebuah contoh. Hal yang sama harus berlaku pada situasi apa pun di mana kita memiliki algoritma yang tidak efisien sepele, dan solusi yang efisien tetapi jauh lebih canggih dari masalah yang sama.

Emil Jeřábek

Teorema speedup Blum biasanya dinyatakan dalam bahasa fungsi rekursif sebagian, tetapi hingga perbedaan sepele dalam notasi, ia bekerja sama saja dalam bahasa -calculus. $\lambda$

Dikatakan bahwa dengan diberikan ukuran kompleksitas yang masuk akal (misalnya, jumlah reduksi optimal seperti dalam pertanyaan) dan fungsi rekursif (misalnya, ), kita dapat menemukan predikat rekursif sedemikian rupa sehingga: $M$ $f(x,y)$ $2^y$ $P(x)$

Untuk setiap algoritma (yaitu, -term dalam bentuk normal di sini) menghitung , ada algoritma lain untuk yang memiliki kecepatan melebihi : $\lambda$ $g$ $P$ $h$ $P$ $f$ $g$
$f (x, M (h, x)) \leq M (g, x) for all large enough inputs x,$ $f(x,M(h,x))\le M(g,x)\text{ for all large enough inputs }x,$

di mana menunjukkan kompleksitas perhitungan pada input sesuai untuk mengukur . $M(g,x)$ $g$ $x$ $M$

Karena itu:

$P$ tidak memiliki algoritma optimal asimptot dalam ukuran yang diberikan
khususnya, algoritma terpendek untuk tidak optimal asimptotik $P$
untuk algoritme apa pun untuk , ada algoritme yang lebih cepat secara asimptotik yang bentuk normalnya lebih panjang (karena hingga penggantian nama variabel, hanya ada banyak istilah normal dengan panjang tertentu) $P$

Emil Jeřábek
sumber

Contoh di mana istilah lambda normal terkecil tidak tercepat

Edit untuk kejelasan

Jawaban: