Pasangan dasar kombinator lengkap paling sederhana untuk ekspresi datar

Dalam makalah Chris Okasaki, " Meratakan Combinators: Surviving Without Parentheses " ia menunjukkan bahwa dua combinator cukup dan diperlukan sebagai dasar untuk menyandikan ekspresi Turing-lengkap tanpa perlu operator aplikasi atau tanda kurung.

Dibandingkan dengan pengkodean logika kombinasional John Trump dalam " Binary Lambda Calculus and Combinatory Logic " melalui pengkodean awalan S dan K combinator dengan operator aplikasi, hanya membutuhkan dua kombinator untuk ekspresi datar meningkatkan kepadatan kode untuk optimalitas. Peta penomoran Goedel yang dihasilkan setiap bilangan bulat ke ekspresi istilah tertutup yang valid dan terbentuk dengan baik, tidak seperti kebanyakan esolang relevan kalkuli dan panjang deskripsi minimal yang representasi kanoniknya biasanya memungkinkan deskripsi program yang tidak valid secara sintaksis.

Namun pengkodean Okasaki dimaksudkan untuk sangat membantu dalam pemetaan satu arah dari istilah kalkulus lambda ke bitstring, tidak harus sebaliknya karena dua kombinator yang digunakan dalam pengurangan ini relatif kompleks ketika digunakan sebagai instruksi substitusi praktis.

Apa pasangan basis kombinator lengkap paling sederhana yang tidak memerlukan operator aplikasi?

Kembali ke ini hampir setahun kemudian, saya menyadari bahwa saya telah melewatkan beberapa penelitian kritis sebelum memposting.

Jot tampaknya sesuai dengan tagihan dari apa yang saya minta, dengan dua combinator B & X yang relatif sederhana yang dapat diwakili oleh penomoran Goedel yang ringkas.

Saya telah menyederhanakan implementasi referensi dengan Python:

def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I

J (n) mengembalikan fungsi dibangun yang menunjukkan program yang diwakili oleh nomor Goedel-nya n.

B (setara dengan Multiplikasi Gereja yang disandikan) melayani fungsi aplikasi fungsional (tanda kurung), dan dapat mengisolasi bagian S / K dari kombinator Iota basis tunggal X.

Ada beberapa sifat penting dari bahasa ini yang saya (hampir) mencuri tanpa malu-malu dari situs web penemu bahasa Chris Barker, sekitar tahun 2000.

Jot adalah bahasa reguler dalam sintaksis tetapi Turing-complete. Anda dapat melihat dari implementasi J (n) bahwa jika bahasa host mendukung rekursi ekor, tidak ada ruang stack yang diperlukan untuk mem-parsing format program bitstring.

Bukti kelengkapan Turing berasal dari situs Chris juga, menerapkan logika kombinatori lengkap Turing yang telah diketahui menggunakan kombinator S dan K:

K  ==> 11100
S  ==> 11111000
AB ==> 1[A][B], where A & B are arbitrary CL combinators built up from K & S

Jot tidak memiliki kesalahan sintaksis, setiap program diberi nomor Goedel dan merupakan program yang valid. Ini mungkin merupakan aspek yang paling penting untuk penelitian saya sendiri, karena tidak hanya menyederhanakan penguraian menjadi hal-hal sepele, tetapi juga dalam teori membuat Jot jauh lebih pelit daripada pengkodean lengkap Turing yang harus melewati program yang cacat.

Saya telah menulis beberapa alat untuk 'memecahkan' melalui brute force masalah semi-diputuskan untuk menemukan kompleksitas fungsi Kolmogorov di Jot. Ia bekerja dengan mengandalkan programmer untuk menentukan beberapa contoh pelatihan yang sangat khas dari pemetaan fungsi, kemudian menghitung semua program Jot sampai semua contoh pelatihan dicocokkan, dan terakhir mencoba bukti kesetaraan fungsi yang ditemukan dengan implementasi verbose asli.

Saat ini hanya berfungsi hingga ~ 40 bit dengan sumber daya terbatas saya. Saya mencoba menulis ulang dengan pemecah SAT untuk mempelajari program yang jauh lebih besar. Jika Anda tahu cara membuka tutup penutupan bersarang sebagai rumus boolean, bantu dengan pertanyaan baru saya .

Sekarang untuk beberapa perbandingan menarik dengan Binary Lambda Calculus karya John Tromp, yang dikenal dengan keringkasannya, tetapi memiliki masalah kemungkinan kesalahan sintaksis. Program-program berikut dihasilkan oleh program pembelajaran saya dalam beberapa detik.

Function    Jot       Binary Lambda Calculus   |J| |B|
--------|----------|--------------------------|---|---
SUCC      J(18400)  "000000011100101111011010" 15  24
CHURCH_0  J(154)    "000010"                    8   6
CHURCH_1  J(0)      "00000111010"               1  11
CHURCH_2  J(588826) "0000011100111010"         20  16
IS_ZERO   J(5)      "00010110000000100000110"   3  23
MUL       J(280)    "0000000111100111010"       9  19
EXP       J(18108)  "00000110110"              15  11
S         J(8)      "00000001011110100111010"   4  23
K         J(4)      "0000110"                   3   7
AND       J(16)     "0000010111010000010"       5  19
OR        J(9050)   "00000101110000011010"     14  20

Dari percobaan saya sendiri, hipotesis bahwa Jot mengarah ke program yang lebih kecil secara perlahan dikonfirmasi ketika program saya mempelajari fungsi-fungsi sederhana, menyusunnya, lalu mempelajari fungsi-fungsi yang lebih besar dari langit-langit yang lebih baik.