Algoritma yang kuat yang terlalu sulit untuk diterapkan — bagaimana memastikan semuanya benar?

9

Saya merujuk pada pertanyaan di sini: algoritma yang kuat terlalu rumit untuk diterapkan .

Jika suatu algoritma kuat, tetapi terlalu rumit untuk diimplementasikan, bagaimana Anda bisa yakin bahwa algoritma itu benar? Tanpa implementasi, Anda tidak akan dapat menguji algoritme dalam skenario dunia nyata, dan algoritme yang sedemikian kompleks dapat berisi bug, yang dapat membatalkan algoritme.

Ini yang tidak saya mengerti; jika Anda memiliki teknik untuk membuktikan kebenaran suatu algoritma, maka Anda sudah memiliki algoritma untuk mengimplementasikannya, bukan? Atau bagaimana kita bisa yakin bahwa teknik pembuktiannya benar?

Saya minta maaf jika saya terdengar dasar!

Perbarui dari Kaveh (direproduksi di sini karena argumennya lebih baik!):

Jika Anda dapat secara formal membuktikan kebenaran suatu algoritma dalam sistem formal seperti Coq maka Anda juga dapat mengekstraksi algoritme tersebut (karena pada dasarnya Anda telah mengimplementasikan algoritme), tetapi fakta kuncinya adalah bahwa untuk sebagian besar algoritma kami tidak memberikan bukti formal tentang kebenaran untuk algoritma, kami menggunakan bukti informal kebenaran. Buktinya bisa salah, yang memang terjadi dari waktu ke waktu, dan bahkan bukti formal dari kebenaran tidak akan membuat kita benar-benar yakin bahwa algoritma itu benar.

ds.algorithms implementation Graviton
sumber
6
Inilah sebabnya kami memiliki teknik untuk membuktikan kebenaran algoritme, meskipun implementasi (benar) pada mesin nyata itu sulit.
Raphael
9
Saya setuju dengan Raphael. Tampak bahwa pertanyaan didasarkan pada asumsi bahwa kebenaran suatu algoritma biasanya dibuktikan dengan mengimplementasikannya, tetapi tidak demikian halnya. Membuktikan kebenaran suatu algoritma dan mengimplementasikan suatu algoritma adalah hal yang sama sekali berbeda, dan satu hal tidak menyiratkan yang lain di kedua arah.
Tsuyoshi Ito
8
Algoritma sederhana dengan bukti kebenaran yang kompleks - bagaimana Anda tahu bahwa mereka benar? Hanya karena suatu algoritma bekerja pada contoh uji tidak berarti itu bekerja pada semua input.
Peter Shor
2
Saya setuju dengan sebagian besar komentar, tetapi saya pikir mereka kehilangan poin kunci. Jika Anda dapat secara formal membuktikan kebenaran suatu algoritma dalam sistem formal seperti Coq maka Anda juga dapat mengekstraksi algoritme tersebut (karena pada dasarnya Anda telah mengimplementasikan algoritme), tetapi fakta kuncinya adalah bahwa untuk sebagian besar algoritma kami tidak memberikan bukti formal tentang kebenaran untuk algoritma, kami menggunakan bukti informal kebenaran. Buktinya bisa salah, itu memang terjadi dari waktu ke waktu, dan bahkan bukti formal dari kebenaran tidak akan membuat kita benar-benar yakin bahwa algoritma itu benar.
Kaveh
5
"Waspadalah terhadap bug dalam kode di atas; Saya hanya membuktikannya benar, tidak mencobanya." ~ Donald Knuth
Lev Reyzin

Jawaban:

11

Beberapa tahun yang lalu, telah terjadi (agak kasar) perdebatan tentang topik yang mirip dengan ini. Semuanya berawal ketika beberapa bukti kompleks ternyata tidak benar, dan beberapa peneliti mulai menimbulkan keraguan tentang sifat dasar bukti (well, saya seharusnya mengatakan "kriptografi yang dapat dibuktikan," tetapi demi kepentingan umum, saya tidak melakukannya) . Kedua belah pihak dari kontroversi menuduh pihak lain salah paham konsep. Berikut tautan untuk info lebih lanjut .

Bukti adalah alat kami (matematis) untuk membuktikan teorema / algoritma yang benar, tetapi ketika mereka menjadi terlalu kompleks, kami mungkin tergelincir dan membuktikan hal-hal yang salah menjadi benar. Bukti 100-halaman terakhir pada P ≠ NP adalah contoh yang bagus. Namun, ini tidak mengesampingkan sifat dasar dari bukti: Tidak ada yang salah dengan mereka.

Satu poin terakhir: Saya pikir mempelajari filsafat sains akan memberi kita lebih banyak wawasan tentang ini. (Di bawah tautan yang diberikan, lihat peluru " Bagaimana kita tahu apakah bukti matematika itu benar? ")

MS Dousti
sumber