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.
sumber
Jawaban:
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:
sumber
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.
sumber
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.
sumber