Bagaimana Anda memeriksa apakah dua algoritma mengembalikan hasil yang sama untuk input apa pun?

17

Bagaimana Anda memeriksa jika dua algoritma (katakanlah, Urutkan gabungan dan Urutkan naif) mengembalikan hasil yang sama untuk input apa pun, ketika set semua input tidak terbatas?

Pembaruan: Terima kasih, Ben, karena telah menjelaskan bagaimana ini tidak mungkin dilakukan secara algoritmik dalam kasus umum. Jawaban Dave adalah ringkasan yang bagus dari metode algoritmik dan manual (tergantung pada kecerdasan manusia dan metafora) yang tidak selalu berfungsi, tetapi cukup efektif.

computability formal-methods software-engineering software-verification Andres Riofrio
sumber
5
seperti kata yuval, tidak ada prosedur yang dapat menentukan itu untuk dua program. tetapi dalam kasus khusus seperti contoh Anda, Anda dapat membuktikannya: misalnya jika Anda membuktikan bahwa kedua algoritma Anda mengembalikan urutan yang diurutkan dan stabil, Anda akan selesai.
Sasho Nikolov
1
Apakah Anda menginginkan teknik / algoritma otomatis atau serangkaian teknik manual?
Dave Clarke
@SashoNikolov, jika kinerja dianggap sebagai bagian dari output, Anda juga harus menunjukkan bahwa keduanya beroperasi dalam kompleksitas ruang / waktu yang sama.
edA-qa mort-ora-y
1
Apakah maksud Anda "memeriksa" atau membuktikan? Apakah maksudnya "input apa saja" atau semua input? Apa motivasi dan konteks pertanyaan itu?
Kaveh
2
@AndresRiorio: Teknik bukti berbeda dari algoritma yang memecahkan masalah umum. Sebagai contoh, masalah penghentian tidak dapat diputuskan tetapi tentu saja mungkin untuk membuktikan penghentian banyak program (dengan tangan atau heuristik otomatis).
Raphael

Jawaban:

16

Berbeda dengan apa yang dikatakan oleh para penentang, ada banyak teknik yang efektif untuk melakukan ini.

  • Bisimulasi adalah satu pendekatan. Lihat misalnya, makalah Gordon tentang Coinduction and Functional Programming .

  • Pendekatan lain adalah dengan menggunakan teori operasional kesetaraan program, seperti karya Pitts .

  • Pendekatan ketiga adalah memverifikasi bahwa kedua program memenuhi spesifikasi fungsional yang sama. Ada ribuan makalah tentang pendekatan ini.

  • Pendekatan keempat adalah menunjukkan bahwa satu program dapat ditulis ulang menjadi yang lain menggunakan transformasi program suara .

Tentu saja tidak satu pun dari metode ini yang lengkap karena tidak dapat dipastikan, tetapi volume dan volume pekerjaan telah diproduksi untuk mengatasi masalah tersebut.

Dave Clarke
sumber
heu · ris · tic . [Gr. εὑρίσκω "temukan"] n. 1. Teknik yang dirancang untuk memecahkan masalah yang mengabaikan apakah solusi dapat dibuktikan benar, tetapi yang biasanya menghasilkan solusi yang baik atau memecahkan masalah yang lebih sederhana yang berisi atau bersinggungan dengan solusi dari masalah yang lebih kompleks. 2. ( Theor. ) Algoritma yang tidak berfungsi.
JeffE
1
Bart Simpson: "Tidak bisa menang. Jangan coba-coba."
Dave Clarke
9
@ Jeff Jeff: Jika Anda ingin memeriksa apakah dua algoritma mengembalikan hasil yang sama, Anda melakukan pembuktian. Ada banyak teknik bagus untuk melakukan ini. Tentu, semua metode tidak lengkap, tetapi siapa yang peduli? Teorema ketidaklengkapan Goedel bukanlah alasan untuk menyerah pada matematika!
Neel Krishnaswami
3
@ JeffE Hanya karena tidak ada fungsi yang dapat dihitung untuk menentukan apakah dua algoritma arbitrer mengembalikan hasil yang sama tidak berarti bahwa Anda tidak dapat menjawab pertanyaan untuk dua algoritma tertentu , terutama karena proses mencari bukti bukanlah komputabel fungsi . Demikian pula ada banyak makalah yang membuktikan pemutusan dijamin untuk algoritma tertentu, terlepas dari kenyataan bahwa itu tidak mungkin untuk ditentukan secara mekanis apakah algoritma sewenang-wenang akan selalu berakhir.
Ben
2
Dalam prakteknya dua algoritma yang seharusnya menghitung fungsi yang sama hampir tidak pernah memungkinkan untuk bukti kesetaraan berbasis bisimulasi. (Dalam kasus algoritma penyortiran yang disebutkan di atas, tahap-tahap per tengah loop / rekursi berbeda.) Saya akan mengatakan menggunakan logika Hoare yang baik untuk menunjukkan bahwa mereka berdua menerapkan spesifikasi yang sama dari perilaku I / O. untuk pergi.
Kai
10

Untuk sedikit menguraikan pernyataan "tidak mungkin", inilah sketsa bukti sederhana.

Kita dapat memodelkan algoritma dengan output oleh Turing Machines yang berhenti dengan output mereka pada rekaman mereka. Jika Anda ingin memiliki mesin yang dapat berhenti dengan menerima dengan output pada rekaman mereka atau menolak (dalam hal ini tidak ada output), Anda dapat dengan mudah membuat pengkodean yang memungkinkan Anda untuk memodelkan mesin ini dengan "berhenti atau berhenti tidak, tidak ada mesin "tolak".

Sekarang, anggap saya memiliki algoritma P untuk menentukan apakah dua TM seperti itu memiliki output yang sama untuk setiap input. Kemudian, diberi TM A dan input X , saya bisa membuat TM B baru yang beroperasi sebagai berikut:

  1. Periksa apakah inputnya persis X
  2. Jika ya, maka masukkan infinite loop
  3. Jika tidak, maka jalankan A pada input

Sekarang saya dapat menjalankan P pada A dan B . B tidak berhenti pada X , tetapi memiliki output yang sama dengan A untuk semua input lainnya, jadi jika dan hanya jika A tidak berhenti pada X maka kedua algoritma ini memiliki output yang sama untuk setiap input. Tetapi P diasumsikan dapat mengetahui apakah dua algoritma memiliki output yang sama untuk setiap input, jadi jika kita memiliki P kita dapat mengetahui apakah mesin arbitrase berhenti pada input yang sewenang-wenang, yang merupakan Masalah Pemutusan. Karena Masalah Pemutusan diketahui tidak dapat diputuskan, P tidak bisa ada.

Ini berarti tidak ada pendekatan umum (yang dapat dihitung) untuk menentukan apakah dua algoritma memiliki output yang sama yang selalu berfungsi, jadi Anda harus menerapkan penalaran khusus pada pasangan algoritma yang Anda analisis. Namun dalam praktiknya mungkin ada pendekatan komputasi yang bekerja untuk kelas besar algoritma, dan pasti ada teknik yang dapat Anda gunakan untuk mencoba mencari bukti untuk kasus tertentu. Jawaban Dave Clarke memberi Anda beberapa hal yang relevan untuk dilihat di sini. Hasil "ketidakmungkinan" hanya berlaku untuk merancang metode generik yang akan menyelesaikan masalah sekali dan untuk semua, untuk semua pasangan algoritma.

Ben
sumber
P
@ Raphael Ya, argumen yang saya buat sketsa mengatakan apa-apa tentang P terbatas seperti itu , hanya saja yang sepenuhnya umum tidak bisa ada. Naluri saya adalah bahwa masalah penghentian masih tidak dapat diputuskan bahkan ketika Anda membatasi untuk "pengurutan algoritma" daripada algoritma umum, dalam hal ini bukti ketidakmungkinan masih berlaku, meskipun saya belum pernah mendengar klaim seperti itu.
Ben
2
Secara lebih umum, teorema Rice menyatakan bahwa tidak ada cara yang dapat dihitung untuk membuktikan sesuatu tentang suatu algoritma, segera setelah setidaknya ada satu algoritma yang memiliki properti yang Anda coba buktikan dan setidaknya satu yang tidak. Misalnya, dengan diberikan algoritme A, tidak ada fungsi yang dapat dihitung yang menggunakan algoritme B sebagai input dan menguji apakah B setara dengan A.
Gilles 'SO-stop being evil'
Penting untuk dicatat bahwa teorema Rice hanya berlaku untuk properti bahasa , bukan pada Mesin Turing (ketika Anda menggunakannya sebagai model "algoritma") Anda. Jika mungkin untuk dua Mesin Turing ada yang keduanya mengenali bahasa yang sama tetapi satu memiliki properti dan yang lainnya tidak, maka teorema Rice tidak berlaku, dan mungkin ada metode yang dapat dihitung secara umum untuk menguji properti. Tapi teorema Rice jelas berlaku untuk kasus ini, ya.
Ben
2

Secara umum itu tidak mungkin, tetapi banyak kendala yang memungkinkan. Misalnya, Anda dapat memeriksa kesetaraan dua program kode garis lurus menggunakan BDD. Eksekusi simbolis dapat menangani banyak kasus lainnya.

James Koppel
sumber
1

Tidak mungkin untuk merancang algoritma yang membuktikan kesetaraan ini secara umum. Petunjuk: pengurangan dari masalah Berhenti.

Yuval Filmus
sumber
Banyak teknik yang ada, meskipun tidak ada yang sepenuhnya otomatis.
Dave Clarke
Saya tidak tahu apakah mungkin atau tidak, dengan jawaban Anda hanya sebuah komentar. bukan jawaban.
@ SaeedAmiri: Saya sedikit memperjelas konteks jawaban; Saya pikir itu cukup lengkap, jika mungkin tidak terlalu bagus.
Raphael
@ Raphael, Pengurangan yang ada dalam pikiran Yuval sudah jelas, dan saya tidak berpikir OP tidak menyadarinya, tetapi masalah sulit IMO adalah menemukan beberapa cara untuk kasus khusus, Jadi pengurangan yang jelas ini bisa menjadi komentar untuk hanya mengingatkan OP untuk kasus umum.
2
@ SaeedAmiri: Itu untuk OP dan pemilih untuk memutuskan saat itu, bukan kita.
Raphael