Apakah evaluator optimal sebenarnya optimal?

10

Istilah berikut (menggunakan bruijn-indeks):

BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0)))))))))

Ketika diterapkan pada nomor gereja, Nevaluasi ke bentuk normal dengan cepat di beberapa evaluator yang ada, termasuk yang naif . Namun, jika Anda menyandikan istilah itu ke jaring interaksi dan mengevaluasinya menggunakan Algoritma Abstrak Lamping, dibutuhkan jumlah eksponensial beta-reduksi terkait dengan N. Di Optlam, secara khusus:

N   interactions(betas)     (BADTERM N)
1   129(72)                 λλλ(1 (2 (2 (2 (2 (2 (2 (2 0))))))))
2   437(205)                λλλ(2 (1 (2 (2 (2 (2 (2 (2 0))))))))
3   976(510)                λλλ(1 (1 (2 (2 (2 (2 (2 (2 0))))))))
4   1836(1080)              λλλ(2 (2 (1 (2 (2 (2 (2 (2 0))))))))
5   3448(2241)              λλλ(1 (2 (1 (2 (2 (2 (2 (2 0))))))))
6   6355(4537)              λλλ(2 (1 (1 (2 (2 (2 (2 (2 0))))))))
7   11888(9181)             λλλ(1 (1 (1 (2 (2 (2 (2 (2 0))))))))
8   22590(18388)            λλλ(2 (2 (2 (1 (2 (2 (2 (2 0))))))))
9   43833(36830)            λλλ(1 (2 (2 (1 (2 (2 (2 (2 0))))))))
10  85799(73666)            λλλ(2 (1 (2 (1 (2 (2 (2 (2 0))))))))
11  169287(147420)          λλλ(1 (1 (2 (1 (2 (2 (2 (2 0))))))))
12  335692(294885)          λλλ(2 (2 (1 (1 (2 (2 (2 (2 0))))))))
13  668091(589821)          λλλ(1 (2 (1 (1 (2 (2 (2 (2 0))))))))
14  1332241(1179619)        λλλ(2 (1 (1 (1 (2 (2 (2 (2 0))))))))
15  2659977(2359329)        λλλ(1 (1 (1 (1 (2 (2 (2 (2 0))))))))

Pada evaluator serupa seperti BOHM, dibutuhkan langkah beta yang jauh lebih sedikit, tetapi lebih banyak interaksi. Jika evaluator optimal optimal, bagaimana mereka bisa mengevaluasi istilah yang secara asimptot lebih lambat dari evaluator yang ada?

Tautan ini memiliki penjelasan tentang asal-usul istilah, serta penerapan fungsi yang sama yang berperilaku sebaliknya, hampir aneh: harus berjalan dalam waktu eksponensial - berjalan dalam waktu eksponensial di sebagian besar evaluator - namun, optimal evaluator menormalkannya dalam waktu linier!

cc.complexity-theory lambda-calculus interaction-nets Viktor Maia
sumber

Jawaban:

5

Efisiensi optlam

Saya belum mempelajari rincian BADTERM atau implementasi evaluator optlam, tetapi saya menemukan cukup aneh bahwa optlam melakukan sejumlah ß-interaksi yang sangat berbeda dari evaluator optimal lainnya seperti BOHM. Angka seperti itu harus, pada dasarnya, pada dasarnya sama dengan istilah yang diberikan. Apakah Anda yakin dengan kebenaran inti optlam?

Efisiensi evaluator optimal

Ingatlah bahwa gagasan optimalitas para evaluator ini lebih tepat dikenal sebagai Optimal-Lévy, dan itu bukan yang naif, karena strategi pengurangan yang melakukan jumlah minimum ß-langkah tidak dapat dihitung. Jadi, yang diminimalkan adalah jumlah langkah reduksi ß paralel yang dilakukan pada seluruh keluarga redex, yaitu kira-kira himpunan yang diperoleh oleh penutupan simetris dan transitif dari relasi yang mengikat dua redeks ketika satu disalin dari yang lain. Seharusnya secara umum tidak mengejutkan untuk melihat perbedaan antara jumlah ß-langkah dan sisa-langkah duplikasi, karena kita tahu bahwa sebagian besar beban normalisasi dapat ditransfer dari yang pertama ke yang terakhir, seperti yang ditunjukkan oleh Asperti, Coppola dan Martini [1].

Seharusnya tidak mengejutkan kita juga untuk melihat bahwa jumlah total interaksi yang diperlukan untuk menormalkan suatu istilah dengan evaluator yang optimal adalah yang lebih rendah daripada dengan yang biasa, karena pengamatan empiris sebelumnya sudah menunjukkan peningkatan kinerja yang menonjol. Namun demikian, lompatan kompleksitas yang begitu besar, dari waktu eksponensial ke linear, mungkin merupakan yang pertama dari jenisnya yang ditemukan. (Saya akan periksa ini.)

Di sisi lain, hasil teoretis tentang efisiensi reduksi optimal (yang merupakan pertanyaan besar Anda), masih sedikit dan belum umum, karena terbatas pada jaring bukti yang diketikkan EAL (yang pada dasarnya merupakan pembatasan optmal yang sama evaluator, jika saya mengerti dengan benar), tetapi semuanya agak positif, karena dalam kasus terburuk kompleksitas pengurangan berbagi dibatasi oleh yang biasa dengan faktor konstan [2,3].

Referensi

  1. A. Asperti, P. Coppola, dan S. Martini, Duplikasi (Optimal) bukan rekursif dasar , Informasi dan Komputasi, vol. 193, 2004.
  2. P. Baillot, P. Coppola, dan U. Dal Lago, Logika cahaya dan reduksi optimal: Kelengkapan dan kompleksitas , Informasi dan Komputasi, vol. 209, tidak. 2, hlm. 118–142, 2011.
  3. S. Guerrini, T. Leventis, dan M. Solieri, Jauh ke dalam optimalitas - kompleksitas dan kebenaran pembagian implementasi logika terikat , DICE 2012, Tallin, Estonia, 2012.
Marco Solieri
sumber
Such a number must be, by definition, basically the same on a given termjadi saya pikir. Itu mengejutkan saya karena Optlam memberikan jumlah beta yang sama dengan BOHM dalam banyak kasus yang saya uji. Namun, dalam beberapa kasus ia memberi lebih sedikit, karena strategi panggilan-oleh-kebutuhannya. Seseorang mengatakan pengurangan tanpa oracle sebenarnya tidak optimal dan sekarang saya tidak tahu lagi. Secara keseluruhan, saya sangat bingung. Tapi tidak, sama sekali tidak ada bukti Optlam beroperasi dengan benar. Saya sedang memikirkan sisa komentar Anda - terima kasih.
MaiaVictor
Selain itu, saya sebenarnya menemukan banyak istilah berbeda yang berperilaku seperti Badterm. Saya mempelajari masalah ini lebih lanjut sehingga saya dapat menemukan istilah yang lebih sederhana yang mereplikasi itu.
MaiaVictor
Semacam strategi panggilan-dengan-kebutuhan paralel adalah standar untuk evaluator yang optimal, termasuk BOHM, karena itu diperlukan untuk optimalisasi Lévy itu sendiri. Oracle tidak sepenuhnya diperlukan untuk secara optimal mengurangi setiap λ-term: istilah bertingkat, seperti yang diketikkan EAL, tidak memerlukannya.
Marco Solieri
Oh, salahku, kalau begitu. Ngomong-ngomong, hanya untuk memastikan saya memahaminya, ketika Anda menghitung duplikasi (bukan hanya beta), mungkin ada istilah yang secara asimptot lebih lambat untuk dikurangi pada evaluator yang optimal, bahkan pada case yang diketikkan EAL? Dalam hal ini, saya ingin tahu mengapa menghitung langkah beta saja dan jika benar-benar ada manfaatnya dalam menggunakan jaring interaksi untuk tujuan pengurangan λ-kalkulus ...
MaiaVictor
1
Aha! Jadi ada istilah non-EAL yang dapat dikurangi tanpa nubuat? Saya berasumsi jika Optlam menguranginya, itu tipe-EAL (karena saya tidak memiliki tipe inferer EAL). Jika bukan itu masalahnya, maka semuanya masuk akal sekarang. Karena himpunan bagian dari istilah-jenis EAL memiliki kekuatan yang cukup untuk mengekspresikan algoritma waktu-poli seperti penyortiran, saya kira akan lebih bijak jika saya secara khusus mencoba merancang istilah-istilah yang dapat jenis-EAL. Saya bertanya-tanya bagaimana hal itu dapat dilakukan dalam praktek. Terima kasih banyak.
MaiaVictor