Seberapa sulit untuk mengurangi penghentian ke kebenaran parsial?

14

Jika Anda terbiasa dengan verifikasi program, Anda cenderung lebih suka membaca Pertanyaan sebelum Latar Belakang . Jika Anda tidak terbiasa dengan verifikasi program maka Anda mungkin masih dapat menjawab pertanyaan ini, tetapi Anda cenderung lebih suka membaca Latar Belakang terlebih dahulu.

Latar Belakang

Sering dinyatakan bahwa memeriksa kebenaran sebagian tidak dapat dipastikan. Demi diskusi, mari kita pilih satu cara yang sangat khusus untuk membuat pernyataan ini tepat, dengan gaya Floyd - Hoare. Sebuah grafik aliran adalah digraf dengan dibedakan simpul awal dari mana semua node dapat dijangkau. Suatu program adalah flowgraph yang simpulnya adalah perintah. Ada tiga jenis perintah (1) asumsi menganggap q , (2) pernyataan menegaskan q , dan (3) tugas v: = e. Di sini q adalah rumus fol (logika orde pertama), e adalah istilah fol, dan v adalah variabel.

Kami mengatakan bahwa suatu program sebagian benar ketika ada cara untuk membubuhi keterangan setiap node x dengan prasyarat a (x) dan postcondition b (x) sedemikian rupa sehingga (1) prasyarat dari simpul awal valid, (2) { a (x) } x { b (x) } berlaku untuk semua perintah x , dan (3) ( b (x) menyiratkan (y) ) berlaku untuk semua tepi dari x ke y . Di sini Hoare tiga kali lipat didefinisikan sebagai berikut:

  • { p } menegaskan q { r } berarti bahwa ( p menyiratkan ( q dan r )) valid
  • { p } menganggap q { r } berarti (( p dan q ) menyiratkan r ) valid
  • { p } v: = e { r } berarti bahwa (( p dengan e tersubstitusi untuk v ) menyiratkan r ) valid

Berikut argumen tangan bergelombang mengapa memeriksa ini kebenaran parsial adalah diputuskan: Setelah Anda mengisi beberapa a (x) dan beberapa b (x) Anda perlu memeriksa apakah beberapa rumus fol adalah valid, dan itu adalah diputuskan.

Cara khas untuk menyandikan penghentian dalam kebenaran parsial adalah dengan menambahkan beberapa pernyataan khusus yang pada dasarnya mengatakan "sejak terakhir kali saya dieksekusi, ada kemajuan menuju penghentian." Pernyataan kemajuan ini harus ditempatkan sedemikian rupa sehingga semua infinite berjalan pada flowgraph (yang dimulai pada simpul awal) mengandung tak terhingga banyaknya pernyataan kemajuan. Untuk lebih spesifik, katakanlah bahwa kemajuan pernyataan selalu memiliki bentuk menegaskan u < v , di mana u dan v adalah bilangan bulat positif, diawali dengan tugas u : = f , dan diikuti oleh tugas v : = u . Di sini f adalah afungsi varian , u adalah nilai saat ini, dan v adalah nilai sebelumnya. Sekarang, karena kita berbicara tentang "bilangan bulat positif" dan kita membandingkannya, kita perlu memastikan bahwa sedikit lebih banyak dari fol tersedia: Katakanlah aritmatika Peano tersedia. (Saya tidak merasa kuat tentang pilihan ini. Jangan menghiraukan jika nyaman.) Tentu saja, f dapat menggunakan fungsi dan konstanta lain yang disebutkan dalam program. (Perhatikan bahwa menambahkan asumsi di awal program setara dengan memperkenalkan aksioma non-logis.)

Sekarang, jika program dengan pernyataan kemajuan masih sebagian benar, maka kita tahu bahwa program asli berakhir.

Pertanyaan

Dengan adanya program terminating, rasanya datang dengan varian fungsi untuk pernyataan kemajuan adalah sulit. Tapi seberapa keras? (Saya tahu bahwa bahkan dengan latar belakang yang sangat besar di atas, saya masih meninggalkan pertanyaan semacam ini terbuka, atau tidak jelas, tergantung pada bagaimana Anda ingin melihatnya.)

Dengan kata lain: Saya mencari referensi yang memformalkan masalah mengurangi penghentian menjadi kebenaran parsial dan kemudian mengatakan sesuatu tentang kompleksitasnya. Jawaban yang melakukan semua ini tentu saja akan diterima.

Radu GRIGore
sumber
Biarkan saya memeriksa apakah saya mengerti ini. Apa yang Anda minta akan memberi kami, antara lain, algoritma yang mengambil program yang menghitung fungsi rekursif total dan mengeluarkan bukti pernyataan bahwa fungsi tersebut total (dalam bentuk fungsi varian dan bukti bahwa mereka cocok )? Kedengarannya sangat sulit bagi saya.
Andrej Bauer
Andrej, kedengarannya tidak dapat dihitung bagi saya juga. Apa yang saya minta adalah bukti bahwa itu tidak dapat dihitung.
Radu GRIGore

Jawaban:

7

Salah satu cara untuk menjawab ini adalah dengan mempertimbangkan kompleksitas komputasi dari masalah keputusan untuk kelas kebenaran parsial dan permintaan terminasi yang diketahui dapat ditentukan. Interpretasi abstrak menggunakan domain polihedral dapat menyimpulkan anotasi kebenaran parsial yang Anda sebutkan dalam kasus-kasus di mana anotasi yang diperlukan adalah konjungsi dari ketidaksetaraan linear. Menghitung kondisi pasca abstrak adalah eksponensial dalam jumlah variabel. Lalu ada overhead menemukan titik tetap. Lihat makalah awal Cousot untuk lebih lanjut tentang ini dan perpustakaan Apron jika Anda ingin bermain dengannya secara langsung.

Menemukan fungsi varian dapat dipilih ketika fungsi varian linier. Saya tidak dapat menemukan karakterisasi lengkap dari kompleksitas ini, tetapi "Pengakhiran Program Linear" oleh Tiwari memiliki bagian yang membahas kompleksitas. Lihat juga "Metode Lengkap untuk Sintesis Fungsi Pemeringkatan Linear" oleh Podelski dan Rybalchenko. Selain itu, Byron Cook telah melakukan upaya meningkatkan interpretasi abstrak untuk membantu membangun argumen pemutusan hubungan kerja. Lihat, misalnya, "Abstraksi Peringkat" dan "Analisis Varians dari Analisis Invarian". Ini dapat memberikan wawasan lebih lanjut tentang hubungan antara kebenaran parsial dan pemutusan hubungan kerja.

Tautan:

Stephen Magill
sumber
1
Saya harap Anda tidak keberatan mengedit jawaban Anda dan membuat tautannya aktif.
Andrej Bauer
4

Ada pengurangan yang jelas dari non-terminasi yang diperlukan ke kebenaran parsial, yaitu:

P tidak pernah berakhir ketika dimulai dalam keadaan awal yang memuaskan φ iff { φ } P {false} valid.

Saya sadar ini bukan jawaban lain. Keuntungannya adalah lebih pendek daripada yang di atas.

Kai
sumber
3

Ada teknologi standar - biasanya tidak dapat diputuskan, tentu saja - untuk mengisi grafik Anda dengan kondisi sebelum dan sesudahnya, yaitu semantik prakondisi liberal terlemah , yang merupakan bentuk semantik transformator predikat yang memberikan prasyarat terlemah baik untuk kepuasan spesifikasi atau non -penghentian. Ini pada dasarnya adalah teori lengkap tentang kebenaran parsial untuk bahasa-bahasa seperti itu, dan, memang, benar sepenuhnya

Ini adalah kapur dan keju yang memutuskan mana dari terminasi dan kebenaran parsial di mana kerja keras terletak, karena keduanya sangat diputuskan. Tetapi kebenaran parsial terjerat dengan masalah desain bahasa, baik untuk bahasa program dan spesifikasi, sementara kesulitan penghentian adalah jenis yang bersih: untuk teori apa pun yang digunakan untuk membuktikan terminasi akan ada algoritma yang berakhir, tetapi konot terbukti terbukti mengakhiri relatif teori itu. Misalnya, perhitungan dalam kalkulus lambda polimorfik murni harus diakhiri, tetapi aritmatika Peano tidak dapat membuktikan hal ini.

Kesan saya adalah bahwa karya interpretasi abstrak dipelopori oleh Patrick Cousot, telah menjadi yang paling dinamis di bidang ini, tetapi saya tidak berpura-pura menjadi ahli.

Charles Stewart
sumber
Saya mencoba untuk bertanya tentang kompleksitas fungsi kesimpulan varian. Maaf karena tidak jelas! Sebagai rasa ingin tahu, Rustan Leino datang dengan contoh tadi malam (di sebuah pub) yang sangat menyarankan kepada saya bahwa wlp tidak berfungsi sebaik wp & sp untuk jenis program yang saya jelaskan di sini. Saya harus mengecek ketika saya sampai di tempat yang lebih cocok untuk bekerja :)
Radu GRIGore
@ Radu: Ada pekerjaan yang dilakukan pada bukti terminasi otomatis, dengan beberapa pekerjaan bagus sedang dilakukan untuk Prolog. Saya dapat menggali beberapa referensi ketika saya menemukan waktu.
Charles Stewart