Apakah kalkulus SK2 merupakan basis yang lengkap, di mana K2 adalah combinator K terbalik?

Khususnya, jika saya mendefinisikan baru sebagai alih-alih akankah -kalkulus menjadi basis kompetisi?$K_2$

Dugaan saya adalah "tidak," hanya karena saya sepertinya tidak dapat membuat kombinator reguler K dari kombinator , , dan , tetapi saya tidak memiliki algoritma untuk diikuti, saya juga tidak memiliki intuisi yang baik tentang membuat sesuatu dari kombinator ini.$S$$I$$K_2$

Sepertinya Anda dapat mendefinisikan dengan reguler -kalkulus, tetapi saya tidak bisa benar-benar bekerja mundur dari itu untuk mendapatkan derivasi dalam hal dan sisanya.

Upaya saya pada bukti bahwa itu tidak lengkap secara fungsional pada dasarnya berusaha untuk membangun secara menyeluruh setiap fungsi yang dapat diperoleh dari kombinator ini untuk menunjukkan bahwa Anda mencapai jalan buntu (fungsi yang telah Anda lihat sebelumnya) tidak peduli kombinator apa yang Anda gunakan. Saya menyadari bahwa ini tidak selalu benar untuk set kombinator yang secara fungsional tidak lengkap (mis. Combinator sendiri tidak akan pernah menemui jalan buntu ketika diterapkan pada dirinya sendiri), tetapi ini adalah pemikiran terbaik saya. Saya selalu dapat menggunakan kombinator untuk menyelinap keluar dari apa yang saya pikir akhirnya menemui jalan buntu, jadi saya tidak lagi yakin dengan kelayakan pendekatan ini.$K$$S$

Saya menanyakan pertanyaan ini di StackOverflow tetapi didorong untuk mempostingnya di sini. Saya menerima beberapa komentar pada posting itu, tetapi saya tidak yakin saya memahaminya dengan benar.

Bonus: jika itu bukan dasar yang lengkap, apakah bahasa yang dihasilkan tetap Turing-lengkap?

Pertimbangkan istilah $S,K_2,I$ kalkulus sebagai pohon (dengan simpul biner mewakili aplikasi, dan $S, K_2$ daun K 2 mewakili kombinator.

Misalnya, istilah $S(SS)K_2$ akan diwakili oleh pohon

        @
       / \
      /   \
     @    K2
    / \
   /   \
  S     @
       / \
      /   \
     S     S

Untuk setiap pohon $T$ mengasosiasikan daun paling kanan, yang Anda dapatkan dengan mengambil cabang kanan pada setiap @. Sebagai contoh, daun paling kanan dari pohon di atas adalah $K_2$ .

Seperti dapat dilihat dari seni ASCII di bawah ini, semua aturan reduksi dalam $S, K_2, I$ kalkulus mempertahankan daun paling kanan.

         @                           @
        / \                         / \
       /   \                       /   \
      @     g    [reduces to]     @     @
     / \                         / \   / \
    /   \                       e   g f   g
   @     f                 
  / \
 /   \
S     e

      @
     / \
    /   \
   @     f    [reduces to]   f
  / \
 /   \
K2    e

Dari sana, mudah untuk melihat bahwa jika beberapa istilah $T$ dikurangi menjadi $T'$ , maka $T$ dan $T'$ memiliki daun paling kanan yang sama. Oleh karena itu, tidak ada istilah $T$ dalam $S, K_2, I$ kalkulus I sehingga $TK_2S$ berkurang menjadi $K_2$ . Namun, $KK_2S$ mengurangi ke $K_2$ , maka $K$ tidak dapat dinyatakan dalam $S,K_2, I$ kalkulus.

EDIT: Seperti komentar menunjukkan, ini hanya jawaban parsial, karena hanya berlaku untuk hanya diketik $S,K_2,I$ kalkulus (atau lebih tepatnya, itu menunjukkan bahwa tidak ada definisi yang mungkin dari K yang tidak mengandung subtipe salah ketik). Jika tidak ada keberatan, saya tidak akan menghapusnya, karena ini menyajikan teknik bukti yang sangat produktif untuk pengaturan yang diketik.

Ingatlah bahwa kombinator kami memiliki tipe berikut (Gaya kari, jadi $A,B,C$ adalah variabel):

• $K: A \rightarrow B \rightarrow A$
• $K_2: A \rightarrow B \rightarrow B$
• $S: (A \rightarrow B \rightarrow C) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)$
• $I: A \rightarrow A$

$K$$I,S,K_2$$A \rightarrow B \rightarrow B, (A \rightarrow B \rightarrow C) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C), A \rightarrow A$$A$$A \rightarrow B$$B$$A \rightarrow B \rightarrow A$

t,f,u$\rightarrow$$A \rightarrow B \rightarrow B$$(A \rightarrow B \rightarrow C) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)$$A \rightarrow A$t

A B | A -> B
t t | t
t f | f
f t | t
f f | t
t u | f
f u | t
u t | t
u f | f
u u | t

$K_2, S, I$tt$A \rightarrow B \rightarrow A$fu$A$t$B$$S, K_2, I$