Combinator universal sekecil mungkin

Saya mencari kombinator universal terkecil yang mungkin , diukur dengan jumlah abstraksi dan aplikasi yang diperlukan untuk menentukan kombinator tersebut dalam kalkulus lambda . Contoh-contoh kombinator universal meliputi:

ukuran 23: λf.f (fS (KKKI)) K
ukuran 18: λf.f (fS (KK)) K
ukuran 14: λf.fKSK
ukuran 12: λf.fS (λxyz.x)
ukuran 11: λf.fSK

di mana S = λxyz.xz (yz) ukuran 6 dan K = λxy.x ukuran 2 adalah kombinator dari kalkulus kombinator SK . 4 contoh pertama dijelaskan dalam makalah ini .

Pertanyaan saya adalah:

Apakah ada kombinator universal yang ukurannya lebih kecil?
Apa kombinator universal terkecil yang mungkin?

EDIT: Lihat juga /math//a/180263/76284 , yang memiliki λazbc.bc(a(λy.c))(yang berukuran 8 , cocok dengan jumlah ukuran dasar SK). Adakah yang tahu cara mengekspresikan S dan K dari kombinator ini?

lo.logic computability lambda-calculus universal-computation combinatory-logic pengguna76284
sumber

Mungkin ini yang menarik: wolframscience.com/nksonline/page-1123a-text?firstview=1

Andrej Bauer

Apa definisi ukuran Anda? Bisakah Anda menulisnya sebagai fungsi?

Joshua Herman

Karena 6 + 2 = 8 <11, ini membuat saya bertanya-tanya apakah {S, K} adalah basis terkecil dari kombinator yang diukur dengan ukuran total?

Noam Zeilberger

Hasil edit terakhir Anda agaknya seperti jawaban (sebagian).

Emil Jeřábek mendukung Monica

Seberapa ketat Anda mendefinisikan " kombinator "? Apakah harus dari bentuk di λx*.Emana Eabstraksi bebas?

Peter Taylor

Jawaban:

Perlu dicatat bahwa menemukan kombinator dengan sifat reduksi tertentu selalu sulit, dan menemukan kombinator terkecil seperti itu mungkin mudah diputuskan (karena alasan sepele, karena mungkin tidak dapat dipastikan untuk membuktikan bahwa aplikasi tertentu kombinatori bahkan berhenti).

Ada beberapa pertanyaan terbuka sederhana dengan rasa yang sama, misalnya masalah # 4, # 6 dan # 10 dari daftar masalah terbuka TLCA .

Satu hal yang perlu diperhatikan adalah bahwa kombinator Anda tentu perlu memiliki setidaknya 2 variabel terikat, salah satunya digandakan (seperti halnya seperangkat kombinator lengkap) dan satu harus dihapus. Ini menempatkan batas bawah 4, saya pikir (2 abstraksi dan 2 penampilan variabel), yang tidak begitu jauh dari batas atas 11.

Sunting: Komentar dan referensi Noam mendorong batas bawah ke 5! Saya tidak akan terkejut jika buktinya juga membutuhkan variabel ekstra untuk muncul juga, yang akan mendorong kita ke 6.

cody
sumber

Sebenarnya, dua variabel tidak cukup ( dl.acm.org/citation.cfm?id=2100917 , cstheory.stackexchange.com/a/36344/674 ), jadi ini memberikan batas bawah yang sedikit lebih tinggi (ukuran 5 = 3 abstraksi dan 2 aplikasi).

Noam Zeilberger

@NoamZeilberger baik-baik saja, itu hasil yang fantastis yang tidak saya sadari!

cody

Untuk pertanyaan pertama Anda, saya yakin makalah ini dapat membantu banyak orang. Ini memiliki kalkulus combinator 6 bit yang juga merupakan UTM. Juga memiliki kombinator universal yang tampaknya memiliki ukuran 7 dengan satu elemen yang diberikan apa yang Anda inginkan. Mereka menyebutnya Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

Saya tidak yakin apakah Anda dapat mengatakan atau membuktikan bahwa ada kombinator minimal. Makalah ini akan menyarankan setidaknya harus kurang dari 6 bit.

Joshua Herman
sumber

Combinator Zot sebenarnya adalah yang terakhir yang tercantum dalam OP: λx.xSK (dibagikan dengan bahasa induknya, Iota dan Jot), yang memiliki panjang 11. Dalam "kalkulus kombinator 6 bit" (Keraia), "6 bit" adalah ukuran UTM; dan sepertinya itu hanya penyandian dari kalkulus lambda, bukan kalkulus kombinator (dan karena itu tidak memiliki kombinator universal bawaan).

Arcampion