Apa yang tidak bisa dilakukan Idris dengan meninggalkan Turing?

Saya tahu bahwa Idris memiliki tipe dependen tetapi belum selesai. Apa yang tidak bisa dilakukan dengan melepaskan kelengkapan Turing, dan apakah ini terkait dengan memiliki tipe dependen?

Saya kira ini adalah pertanyaan yang cukup spesifik, tetapi saya tidak tahu banyak tentang tipe dependen dan sistem tipe terkait.

Idris Turing Lengkap! Itu memeriksa totalitas (penghentian saat pemrograman dengan data, produktivitas saat pemrograman dengan codata) tetapi tidak mengharuskan semuanya total.

Menariknya, memiliki data dan kodata cukup untuk model Kelengkapan Turing karena Anda dapat menulis monad untuk fungsi parsial. Saya melakukan ini, tahun lalu, di Coq - mungkin sudah bitrotted sekarang tapi ini dia: http://eb.host.cs.st-andrews.ac.uk/Partial/partial.v .

Anda memang perlu satu pelarian untuk benar-benar menjalankan hal-hal seperti itu, tetapi Idris memungkinkan Anda untuk melakukan itu.

Idris tidak akan mengurangi fungsi parsial pada tingkat tipe, agar pemeriksaan jenis dapat dimenangkan. Juga, hanya total program yang dapat dipercaya sebagai bukti.

Pertama, saya menganggap Anda sudah pernah mendengar tentang tesis Gereja-Turing , yang menyatakan bahwa apa pun yang kita sebut "perhitungan" adalah sesuatu yang dapat dilakukan dengan mesin Turing (atau salah satu dari banyak model lain yang setara). Jadi bahasa Turing-complete adalah bahasa di mana perhitungan apa pun dapat diekspresikan. Sebaliknya, bahasa Turing-tidak lengkap adalah bahasa di mana ada beberapa perhitungan yang tidak dapat diungkapkan.

Oke, itu tidak terlalu informatif. Izinkan saya memberi contoh. Ada satu hal yang tidak dapat Anda lakukan dalam bahasa Turing-tidak lengkap: Anda tidak dapat menulis simulator mesin Turing (jika tidak, Anda dapat menyandikan perhitungan apa pun pada mesin Turing yang disimulasikan).

Ok, masih tidak terlalu informatif. pertanyaan sebenarnya adalah, apa yang berguna program yang tidak dapat ditulis dalam bahasa Turing-tidak lengkap? Yah, tidak ada yang datang dengan definisi "program yang berguna" yang mencakup semua program yang ditulis seseorang di suatu tempat untuk tujuan yang bermanfaat, dan itu tidak termasuk semua perhitungan mesin Turing. Jadi merancang bahasa Turing-tidak lengkap di mana Anda dapat menulis semua program yang bermanfaat masih merupakan tujuan penelitian jangka panjang.

Sekarang ada beberapa jenis bahasa Turing yang tidak lengkap di luar sana, dan mereka berbeda dalam hal apa yang tidak dapat mereka lakukan. Namun ada tema umum: Bahasa Turing-complete harus menyertakan beberapa cara untuk mengakhiri secara kondisional atau tetap berjalan untuk waktu yang tidak dibatasi oleh ukuran program, dan cara bagi program untuk menggunakan jumlah memori yang tergantung pada input . Konkretnya, sebagian besar bahasa pemrograman imperatif menyediakan kemampuan ini melalui loop sementara dan alokasi memori dinamis masing-masing. Sebagian besar bahasa pemrograman fungsional menyediakan kemampuan ini melalui rekursi dan struktur data bersarang.

Idris sangat terinspirasi oleh Agda . Agda adalah bahasa yang dirancang untuk membuktikan teorema . Sekarang membuktikan teorema dan menjalankan program-program yang sangat erat terkait , sehingga Anda dapat menulis program di Agda seperti Anda membuktikan teorema. Secara intuitif, bukti teorema "A menyiratkan B" adalah fungsi yang mengambil bukti teorema A sebagai argumen dan mengembalikan bukti teorema B.

Karena tujuan dari sistem ini adalah untuk membuktikan teorema, Anda tidak dapat membiarkan programmer menulis fungsi yang sewenang-wenang. Bayangkan bahasa yang memungkinkan Anda untuk menulis fungsi rekursif konyol yang hanya menyebut dirinya:

oops : A -> B
oops x = oops x

Anda tidak dapat membiarkan keberadaan fungsi seperti itu meyakinkan Anda bahwa A menyiratkan B, atau Anda akan dapat membuktikan apa pun dan bukan hanya teorema yang benar! Jadi Agda (dan pembalik teorema serupa) melarang rekursi sewenang-wenang. Ketika Anda menulis fungsi rekursif, Anda harus membuktikan bahwa itu selalu berakhir , sehingga setiap kali Anda menjalankannya pada bukti teorema A Anda tahu bahwa itu akan membangun bukti teorema B.

Keterbatasan praktis langsung dari Agda adalah bahwa Anda tidak dapat menulis fungsi rekursif sewenang-wenang. Karena sistem harus dapat menolak semua fungsi non-terminasi, ketidakpastian masalah penghentian (atau lebih umum teorema Rice ) memastikan bahwa ada fungsi terminasi yang ditolak juga. Kesulitan praktis tambahan adalah bahwa Anda harus membantu sistem untuk membuktikan bahwa fungsi Anda berakhir.

Ada banyak penelitian yang sedang berlangsung untuk membuat sistem bukti lebih seperti bahasa pemrograman tanpa mengurangi jaminannya bahwa jika Anda memiliki fungsi dari A ke B, sama baiknya dengan bukti matematis yang disiratkan oleh A. Memperluas sistem untuk menerima lebih banyak mengakhiri fungsi adalah salah satu topik penelitian. Arah ekstensi lainnya termasuk mengatasi masalah "dunia nyata" seperti input / output dan konkurensi. Tantangan lain adalah membuat sistem ini dapat diakses oleh manusia biasa (atau mungkin meyakinkan manusia biasa bahwa mereka sebenarnya dapat diakses).

Saya tidak terbiasa dengan Idris. Ini adalah tantangan yang baru saja saya sebutkan. Sejauh yang saya mengerti dari pandangan sekilas pada 2013 preprint , Idris adalah Turing-lengkap, tetapi mencakup checker totalitas. Pemeriksa totalitas memverifikasi bahwa setiap fungsi yang dijelaskan dengan kata kunci totalberakhir. Fragmen bahasa yang hanya berisi program Idris di mana setiap fungsi total sama dalam kekuatan ekspresif dengan Arda (mungkin bukan pencocokan persis karena perbedaan dalam teori jenis, tetapi cukup dekat sehingga Anda tidak akan melihat kecuali Anda sengaja mencoba).

Untuk contoh bahasa lain yang tidak menyelesaikan Turing dengan cara yang berbeda, lihat Apa batasan praktis dari bahasa lengkap yang tidak menggunakan turing seperti Coq? (jawaban ini untuk sebagian besar diambil dari).