Bisakah mengetikkan lambda calculi mengekspresikan * semua * algoritma di bawah kompleksitas yang diberikan?

Saya tahu bahwa kompleksitas sebagian besar varietas kalkulus lambda yang diketik tanpa primitif combinator Y dibatasi, yaitu hanya fungsi kompleksitas yang dibatasi yang dapat diekspresikan, dengan batas menjadi lebih besar ketika ekspresi dari sistem tipe tumbuh. Saya ingat bahwa, misalnya, Kalkulus Konstruksi dapat mengekspresikan kompleksitas eksponensial yang paling ganda.

Pertanyaan saya menyangkut apakah kalkulus lambda yang diketik dapat mengekspresikan semua algoritma di bawah batas kompleksitas tertentu, atau hanya beberapa? Misalnya, apakah ada algoritma waktu eksponensial yang tidak dapat diungkapkan oleh formalisme apa pun di Lambda Cube? Apa "bentuk" ruang kompleksitas yang sepenuhnya ditutupi oleh berbagai sudut kubus?

Saya akan memberikan jawaban parsial, saya berharap orang lain akan mengisi kekosongan.

Dalam diketik -calculi, satu dapat memberikan tipe representasi biasa data ( N a t untuk Gereja (unary) bilangan bulat, S t r untuk string biner, B o o l untuk Booleans) dan bertanya-tanya apa yang kompleksitas fungsi / masalah diwakili / decidable oleh istilah yang diketik. Saya tahu persis asnwer hanya dalam beberapa kasus, dan dalam kasus yang diketik sederhana itu tergantung pada konvensi yang digunakan ketika mendefinisikan "representable / decidable". Bagaimanapun, saya tidak tahu ada kasus di mana ada batas atas eksponensial ganda.$\lambda$$\mathsf{Nat}$$\mathsf{Str}$$\mathsf{Bool}$

Pertama, rekap singkat di Lambda Cube. 8 kalkulusnya diperoleh dengan mengaktifkan atau menonaktifkan 3 jenis dependensi berikut di atas -calculus (STLC) yang diketik sederhana :$\lambda$

• polimorfisme : istilah mungkin tergantung pada jenis;
• tipe dependen : tipe dapat bergantung pada ketentuan;
• urutan yang lebih tinggi : tipe mungkin tergantung pada tipe.

(Ketergantungan syarat pada persyaratan selalu ada).

Menambahkan polimorfisme yield Sistem F. Di sini, Anda dapat mengetik bilangan bulat Gereja dengan , dan demikian pula untuk string biner dan Boolean. Girard membuktikan bahwa persyaratan Sistem F tipe N a t → N a t mewakili fungsi numerik yang totalitasnya dapat dibuktikan dalam aritmatika Peano orde kedua. Itu cukup banyak matematika sehari-hari (walaupun tanpa bentuk pilihan), sehingga kelasnya sangat besar, fungsi Ackermann adalah semacam mikroba kecil di dalamnya, apalagi fungsi 2 $\mathsf{Nat}:=\forall X.(X\rightarrow X)\rightarrow X\rightarrow X$$\mathsf{Nat}\rightarrow\mathsf{Nat}$ . Saya tidak tahu adanya fungsi numerik "alami" yang tidak dapat direpresentasikan dalam Sistem F. Contoh biasanya dibangun oleh diagonalisasi, atau penyandian konsistensi PA orde dua, atau trik referensial diri lainnya (seperti menentukanβ-kesetaraan dalam Sistem F sendiri). Tentu saja dalam Sistem F Anda dapat mengkonversi antara bilangan bulat unaryNatdan mereka representasi binerStr, dan kemudian menguji misalnya apakah bit pertama adalah 1, sehingga kelas masalah decidable (oleh hal jenisStr→Bool) sama besarnya.$2^{2^n}$$\beta$$\mathsf{Nat}$$\mathsf{Str}$$\mathsf{Str}\rightarrow\mathsf{Bool}$

Oleh karena itu 3 kalkulus lain dari Lambda Cube yang mencakup polimorfisme setidaknya sama ekspresifnya dengan Sistem F. Ini termasuk Sistem F ym (polimorfisme + tatanan yang lebih tinggi), yang dapat mengekspresikan dengan tepat fungsi total yang dapat dibuktikan dalam orde tinggi PA, dan Kalkulus dari Konstruksi (CoC), yang merupakan kalkulus paling ekspresif dari Cube (semua dependensi diaktifkan). Saya tidak tahu karakterisasi dari ekspresifitas CoC dalam hal teori aritmetika atau teori himpunan, tetapi pasti cukup menakutkan :-)$_\omega$

Saya jauh lebih bodoh tentang kalkuli yang diperoleh dengan hanya mengaktifkan tipe dependen (pada dasarnya teori tipe Martin-Lof tanpa persamaan dan angka alami), tipe orde yang lebih tinggi atau keduanya. Dalam kalkuli ini, tipenya sangat kuat tetapi istilah tidak dapat mengakses kekuatan ini, jadi saya tidak tahu apa yang Anda dapatkan. Secara komputasi, saya tidak berpikir Anda mendapatkan lebih banyak ekspresif daripada dengan tipe sederhana, tapi saya mungkin salah.

Jadi kita dibiarkan dengan STLC. Sejauh yang saya tahu, ini adalah satu-satunya kalkulus dari Cube dengan batas atas kompleksitas yang menarik (yaitu, tidak terlalu besar). Ada pertanyaan yang belum terjawab tentang ini di TCS.SE, dan kenyataannya situasinya agak halus.

Pertama, jika Anda memperbaiki atom dan mendefinisikan N a t : = ( X → X ) → X → X , ada hasil Schwichtenberg (saya tahu ada terjemahan bahasa Inggris dari kertas itu di suatu tempat di web tetapi saya tidak dapat menemukannya sekarang) yang memberi tahu Anda bahwa fungsi tipe N a t → N a t adalah persis polinomial yang diperluas (dengan if-then-else). Jika Anda mengizinkan beberapa "slack", yaitu Anda mengizinkan parameter X untuk dipakai sesuka hati dan mempertimbangkan ketentuan tipe N a t$X$$\mathsf{Nat}:=(X\rightarrow X)\rightarrow X\rightarrow X$$\mathsf{Nat}\rightarrow\mathsf{Nat}$$X$ dengan A sewenang - wenang, lebih banyak lagi yang bisa diwakili. Misalnya, sembarang menara eksponensial (sehingga Anda dapat melampaui eksponensial dua kali lipat) maupun fungsi pendahulunya, tetapi masih tidak ada pengurangan (jika Anda mempertimbangkan fungsi biner dan mencoba mengetiknya dengan N a t [ A ] → N a t [ A ′ ] → N a t ). Jadi kelas fungsi numerik yang diwakili dalam STLC agak aneh, itu adalah subset ketat dari fungsi-fungsi dasar tetapi tidak sesuai dengan apa pun yang diketahui.$\mathsf{Nat}[A]\rightarrow\mathsf{Nat}$$A$$\mathsf{Nat}[A]\rightarrow\mathsf{Nat}[A']\rightarrow\mathsf{Nat}$

Dalam kontradiksi dengan di atas, ada tulisan ini dengan Mairson yang menunjukkan bagaimana untuk mengkodekan fungsi transisi dari sewenang-wenang mesin Turing , dari mana Anda mendapatkan jangka tipe N sebuah t [ A ] → B o o l (untuk beberapa jenis A tergantung pada M ) yang, diberikan bilangan bulat Gereja n sebagai input, mensimulasikan pelaksanaan M mulai dari konfigurasi awal yang tetap untuk sejumlah langkah dalam bentuk 2 2 ⋮ 2 n$M$$\mathsf{Nat}[A]\rightarrow\mathsf{Bool}$$A$$M$$n$$M$

$$2^{2^{\vdots^{2^n}}},$$ dengan ketinggian menara diperbaiki. Ini tidak menunjukkan bahwa setiap masalah dasar dapat diputuskan oleh STLC, karena dalam STLC tidak ada cara untuk mengkonversi string biner (dari tipe ) yang mewakili input M ke tipe yang digunakan untuk mewakili konfigurasi M di Pengkodean Mairson. Jadi pengkodeannya entah bagaimana "tidak seragam": Anda dapat mensimulasikan eksekusi yang lama secara elementer dari input tetap, menggunakan istilah berbeda untuk setiap input, tetapi tidak ada istilah yang menangani input sewenang-wenang.$\mathsf{Str}$$M$$M$

$\mathcal C_{ST}$$\mathsf{Str}[A]\rightarrow\mathsf{Bool}$$A$$\mathcal C_{ST}$$\mathcal C_{ST}\subsetneq\mathrm{LINTIME}$$\mathrm{LINTIME}\setminus\mathcal C_{ST}$

---

$\mathcal C_{ST}$

$\mathcal C_{ST}=\mathsf{REG}$$\{0,1\}$

(Ini Teorema 3.4 di makalah mereka).

$\mathcal C_{ST}$$\mathrm{LINTIME}$$\lambda$$\mathcal C_{ST}$

(Kebetulan, saya berbagi keterkejutan saya dalam jawaban ini untuk pertanyaan MO tentang "teorema tidak diketahui").

Sebuah jawaban untuk pertanyaan yang diajukan Damiano dalam jawabannya yang luar biasa:

Saya jauh lebih bodoh tentang kalkuli yang diperoleh dengan hanya mengaktifkan tipe dependen (pada dasarnya teori tipe Martin-Lof tanpa persamaan dan angka alami), tipe orde yang lebih tinggi atau keduanya. Dalam kalkuli ini, tipenya sangat kuat tetapi istilah tidak dapat mengakses kekuatan ini, jadi saya tidak tahu apa yang Anda dapatkan.

$_\omega$

$\lambda{P}$$\lambda{P}\omega$

Saya tidak tahu apa kekuatan kalkulus konstruksi impredikatif, jika Anda menambahkan jenis induktif dan eliminasi besar.

Saya akan mencoba untuk melengkapi jawaban Damiano yang sangat baik.

$\lambda$$F$ $\mathrm{HA}_2$

$\cal{T}$$\cal{L}$$\cal{T}$$\cal{L}$

$\cal{L}$

• $F$$\mathrm{HA}_2$

• $T$$\mathrm{PA}$$F$

$\lambda$$\mathrm{PTIME}$

Secara umum ini adalah jalan besar penelitian, jadi saya hanya akan merujuk ke salah satu jawaban saya sebelumnya .