Kelas fungsi yang dihitung oleh Coq

22

Karena itu tidak memungkinkan perhitungan nonterminating, Coq tentu tidak Turing-lengkap. Apa kelas fungsi yang dapat dihitung Coq? (Adakah karakterisasi yang menarik darinya?)

computability pl.programming-languages coq Steve
sumber

Jawaban:

18

Benjamin Werner telah membuktikan kemampuan saling menafsirkan ZFC dengan banyak sekali akses dan Kalkulus Konstruksi Induktif, dalam makalahnya Sets in Types, Types in Sets .

Ini berarti, secara kasar, bahwa fungsi apa pun yang dapat ditunjukkan sebagai total dalam ZFC dengan banyak sekali akses yang tidak dapat dapat didefinisikan dalam Coq. Jadi, kecuali jika Anda adalah seorang ahli teori yang bekerja pada kardinal besar, kecil kemungkinan fungsi komputasi yang Anda inginkan tidak dapat didefinisikan dalam Coq.

Neel Krishnaswami
sumber
7
Kecuali seorang juru bahasa Coq ...
Jules
6
Sebenarnya, Anda bisa mengimplementasikan juru bahasa Coq (memang, fungsi rekursif umum sewenang-wenang) di dalam Coq. Jika CIC konsisten, Anda tidak akan dapat membuktikan bahwa penerjemah adalah fungsi total, tentu saja, tetapi Anda pasti dapat menerapkannya.
Neel Krishnaswami
2
c o n t e x t → t e r m → t y p e → b o o l ⊥A⊥≜να.A+αcontext→term→type→bool⊥
1
@Neel: Itu curang. Dan untuk alasan yang baik, kalau tidak kita akan memiliki inkonsistensi.
Andrej Bauer
2
Itu curang karena fungsi evaluasi seharusnya mengevaluasi hal-hal, tidak memberi Anda jawaban.
Andrej Bauer