Apakah MALL + tipe rekursif tak terbatas Turing-lengkap?

Jika Anda melihat kombinator rekursif dalam lambda-kalkulus yang tidak diketik, seperti kombinator Y atau kombinator omega: Jelas bahwa semua kombinator ini akhirnya menduplikasi suatu variabel dalam definisi mereka.

\begin{array}{lcl} ω & = & (λ x . x x) (λ x . x x) \\ Y & = & λ f . (λ x . f (x x)) (λ x . f (x x)) \end{array}

$\begin{array}{lcl} \omega & = & (\lambda x.\,x\;x)\;(\lambda x.\,x\;x)\\ Y & = & \lambda f.\,(\lambda x.\,f\;(x\;x))\; (\lambda x.\,f\;(x\;x)) \\ \end{array}$

Selain itu, semua kombinator ini dapat diketik dalam kalkulus lambda yang diketik sederhana, jika Anda memperluasnya dengan tipe rekursif , di mana dibiarkan terjadi secara negatif dalam tipe rekursif. $\mu\alpha.\,A(\alpha)$ $\alpha$

Namun, apa yang terjadi jika Anda menambahkan tipe rekursif penuh (negatif-kejadian) ke fragmen bebas logika linear eksponensial (yaitu, MALL)?

Maka Anda tidak memiliki eksponensial untuk memberi Anda kontraksi. Anda dapat menyandikan jenis eksponensial menggunakan sesuatu seperti $!A$ tetapi saya tidak melihat cara mendefinisikan aturan pengantar untuk itu, karena itu sepertinya memerlukan kombinator titik tetap untuk mendefinisikan. Dan saya mencoba mendefinisikan eksponensial, untuk mendapatkan kontraksi, untuk mendapatkan kombinator titik tetap!

! SEBUAH ≜ μ α . saya & SEBUAH & (α \otimes α)

$!A \triangleq \mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)$

Apakah ini kasus bahwa MALL ditambah tipe rekursif tak terbatas masih menjadi normal‽

lo.logic pl.programming-languages linear-logic Neel Krishnaswami
sumber

Saya memikirkan hal ini beberapa hari yang lalu, dan menghabiskan beberapa jam untuk bermain-main dengan beberapa ide tetapi tidak dapat menemukan cara untuk mengekspresikan nilai rekursif atau meyakinkan diri saya bahwa itu tidak mungkin. Intuisi saya adalah tidak! Saya tidak mempertimbangkan arah lain - jika Anda menganggap aturan pengantar untuk! dan tipe rekursif, apakah itu memungkinkan Anda menentukan kombinator titik tetap?

CA McCann

Saya selalu berpikir bahwa

-term di mana setiap variabel terjadi paling banyak sekali adalah dapat diketik dalam fragmen yang diketik sederhana. Jadi itu akan menunjukkan Anda tidak dapat menentukan kombinator fixpoint di mana variabel digunakan secara linear.

λ

$\lambda$

Andrej Bauer

Saya pikir Anda baru saja menjawab pertanyaan bagi MLL, tapi aditif

melakukan memungkinkan variabel yang akan digandakan (linearitas kemudian menyiratkan kejadian tunggal dalam urutan penurunan, kasar).

A & B

$A & B$

Neel Krishnaswami

Jika pergantian aditif dihilangkan dalam MALL, mudah untuk menunjukkan bahwa ukuran bukti berkurang dengan setiap langkah eliminasi potong. Jika pergantian aditif diizinkan, buktinya tidak mudah, tetapi diberikan dalam kertas "Linear Logic" asli. Ini disebut Teorema Normalisasi Kecil (Konsol 4.22, p71), yang mengatakan bahwa selama aturan kontraksi-promosi tidak dilibatkan (yang merupakan kasus di MALL) berlaku normalisasi. Argumen tidak bergantung pada rumus itu sendiri, mereka bisa tak terbatas (misalnya didefinisikan secara rekursif).

$\mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)$

$\mu$ $!A$

Stéphane Gimenez
sumber

Juga perhatikan bahwa jenis yang disarankan disebutkan secara singkat di halaman 101 (halaman terakhir) dari makalah ini.

Stéphane Gimenez

Apakah MALL + tipe rekursif tak terbatas Turing-lengkap?

Jawaban: