Set dasar untuk kalkulus combinator

Telah diketahui secara umum bahwa kombinator S dan K membentuk dasar yang ditetapkan untuk kalkulus kombinator, dalam arti bahwa semua kombinator lainnya dapat diekspresikan sesuai dengan kombinasinya. Ada juga B Curry's B, C, K, W, yang memiliki properti yang sama. Pasti ada jumlah pangkalan yang tak terbatas, tetapi saya tidak tahu yang lain.

Saya sadar bahwa ada sejumlah pangkalan kombinator tunggal, seperti kombinator Iota dan berbagai pangkalan lainnya yang dibangun / diulas oleh Fokker . Namun, ini adalah kombinator yang "tidak tepat", yang berarti bahwa kombinasinya dinyatakan dalam kombinator lain daripada abstraksi murni. ¹ Untuk keperluan pertanyaan ini, saya hanya tertarik pada set basis yang terdiri dari kombinator yang tepat.

Apakah ada juga studi tentang set dasar lainnya yang mungkin? Ideal akan menjadi sesuatu di sepanjang garis studi Wolfram tentang berbagai model komputasi lain, di mana berbagai kombinasi dipelajari secara sistematis. Secara khusus, saya tertarik pada apakah contoh sederhana dari hal-hal berikut diketahui:

• Satu set dasar minimal yang mencakup combinator I. (Saya menggunakan "minimal" untuk berarti bahwa jika Anda menghapus anggota mana pun itu berhenti menjadi basis, sehingga basis SKI tidak akan dihitung.)
• Sebuah minimal basis set yang mencakup combinator Y, atau combinator (alias mockingbird)$\omega$

Setiap informasi lain tentang basis-basis lain yang mungkin untuk logika kombinasi selain S, K dan B, C, K, W akan sangat membantu.

Sebagai poin yang lebih luas, saya tertarik pada studi tentang kalkulus kombinasi sebagai sistem mekanis murni , yaitu sebagai seperangkat aturan transformasi pada pohon biner dengan node berlabel, yang tidak perlu diberikan interpretasi semantik tertentu. Setiap petunjuk terhadap sumber daya yang menggunakan pendekatan ini akan sangat dihargai. ( Untuk Mock a Mockingbird mengambil pendekatan ini tetapi memberikan presentasi yang tidak lengkap, sedangkan Barendregt's Lambda Calculus sangat terkait dengan semantik, sehingga sulit bagi saya untuk mengekstrak aspek mekanis murni yang saya tertarik.)

^{1 Lebih} _{tepatnya: dalam kalkulus lambda kombinator yang tepat adalah ekspresi dari bentuk , di mana P ( x 1 , x 2 , ... ) hanya memiliki x 1 , x 2 dll sebagai variabel bebas, dan tidak mengandung abstraksi apa pun. Jadi misalnya, ( λ x y z . X ( $(\lambda.x_1x_2\dots P(x_1,x_2,\dots))$$P(x_1,x_2,\dots)$$x_1$$x_2$ adalah kombinator yang tepat, tetapi ( λ x . x ( λ y . y ) ) tidak, karena mengandung x yang diterapkan pada istilah lambda.$(\lambda x y z. x(z z))$$(\lambda x. x(\lambda y.y) )$$x$}

$C$$T = (\lambda x y. y x)$$W$$\omega = (\lambda x. x x)$$C$$W$$C = B(T(B B T))(B B T)$$W = C(B \omega(B B T))$

Setiap set kombinator yang berisi kombinator pembatalan (seperti K), kombinator pengarang (seperti B), kombinator permutasi (seperti C), kombinator duplikat (seperti W) dan kombinator identitas I adalah dasar. Jika kombinator saya berasal dari empat kombinator Anda yang lain, maka keempat kombinator itu saja sudah cukup.

Ini berarti bahwa sesuatu seperti B, T, M, K, I, di mana Tab = ba dan Ma = aa, juga merupakan basis. Memang, B, T, M, K sudah mencukupi, karena saya mungkin diturunkan dari B, T, M, K (ini tidak mudah untuk dibuktikan; buktinya adalah pertama-tama diperoleh S dari B, T, M dan kemudian ambil I = SKK.)