Contoh algoritma yang tidak memiliki bukti kebenaran

Kami memiliki logika Hoare. Mengapa masih mungkin bahwa suatu algoritma itu benar tetapi tidak ada bukti bahwa itu benar? Misalkan algoritma dinyatakan dalam C. Kemudian kita dapat berdebat langkah demi langkah bahwa itu melakukan apa yang seharusnya dilakukan.

Jadi pertanyaan saya adalah:

Berikan saya contoh algoritma yang benar tetapi tidak memiliki bukti kebenaran.

EDIT: Saya pikir sedikit latar belakang dapat membantu memperjelas ke mana saya akan pergi. Biarkan saya mengutip Scott Aaronson:

Sejak tahun 1970-an, telah ada spekulasi bahwa P $\ne$ NP mungkin independen (yaitu, tidak dapat dibuktikan atau disangkal) dari sistem aksioma standar untuk matematika, seperti teori himpunan Zermelo-Fraenkel. Agar lebih jelas, ini juga berarti itu

1. algoritma polinomial-waktu untuk masalah NP-complete tidak ada, tetapi kita tidak pernah bisa membuktikannya (setidaknya tidak dalam sistem formal kita yang biasa), atau yang lain

2. algoritma polinomial-waktu untuk masalah NP-complete memang ada, tetapi kita tidak pernah bisa membuktikan bahwa itu berfungsi, atau kita tidak pernah dapat membuktikan bahwa ia berhenti pada waktu polinomial.

Saya mengacu pada kemungkinan kedua. Karena Aaronson dapat dengan percaya diri mendaftarkannya sebagai kemungkinan, saya pikir pasti ada contoh tipe 2. yang ada. Itulah mengapa saya mengajukan pertanyaan ini. Namun sepertinya jawaban yang cepat dan jelas tidak terlihat.

Berikut ini adalah algoritma untuk fungsi identitas:

• Input: $n$
• Periksa apakah string biner ke- mengkodekan bukti 0 > 1 dalam ZFC, dan jika demikian, hasilkan n + $n$$0 > 1$$n+1$
• Jika tidak, output $n$

Kebanyakan orang menduga algoritma ini menghitung fungsi identitas, tetapi kami tidak tahu, dan kami tidak dapat membuktikannya dalam kerangka yang diterima secara umum untuk matematika, ZFC .

Sebagian besar algoritma belum terbukti benar dalam logika Hoare. Alasan utama adalah bahwa bukti ketepatan seperti itu sangat mahal pada Januari 2017, mungkin oleh beberapa urutan besarnya dibandingkan dengan pemrograman 'belaka'. Ada banyak pekerjaan berkelanjutan untuk mengurangi biaya ini dengan otomatisasi, tetapi ini adalah perjuangan yang berat.

Alasan lain mengapa suatu algoritma mungkin tidak memiliki bukti kebenaran, dan satu yang lebih relevan dalam praktik daripada fenomena ketidaklengkapan yang disebutkan Yuval dan chi, adalah bahwa kita mungkin tidak tahu apa spesifikasi ini. Masalah ini memiliki dua dimensi.

• Pelanggan tidak tahu apa yang mereka inginkan. Ini adalah masalah yang terkenal dalam rekayasa perangkat lunak, dan insinyur perangkat lunak telah mengembangkan banyak pendekatan untuk mengatasi hal ini.

• Spesifikasinya sulit. Contoh yang baik adalah kebenaran dari algoritma kriptografi. Hanya baru-baru ini Micali & Goldwasser memenangkan penghargaan Turing untuk menentukan apa arti keamanan kriptografi. Namun perlu dicatat bahwa definisi itu (sejauh yang saya ketahui) untuk "kriptografi teoretis" di mana Anda memiliki parameter keamanan $n$mulai dari bilangan asli, dan musuh adalah mesin Turing probabilistik waktu polinomial. Sejauh pengetahuan saya (tolong perbaiki saya jika saya salah) ada ketidakcocokan antara teori dan praktik, dan algoritma konkret seperti AES dan SHA256 tidak cukup dalam lingkup spesifikasi teoritis tersebut. Saya tidak berpikir ada spesifikasi lengkap untuk algoritma seperti itu, maka kita tidak bisa, pada prinsipnya memverifikasi mereka dalam arti logika misalnya Hoare.

Ini terkait dengan ketidaklengkapan dari logika yang mendasarinya. Memang, logika Hoare biasanya berisi aturan "post" yang melemah atau

$P(n)$$P(0)$$P(1)$$P(2)$$\forall n\in \mathbb{N}.\ P(n)$

$M$$n$$P(n)$$M$$\forall n.\ P(n)$$M$$\forall n.\ P(n)$

Masalah: Cetak "Ya" jika setiap angka genap ≥ 4 adalah jumlah dua bilangan prima, dan "Tidak" jika ada bilangan genap ≥ 4 yang bukan jumlah dua bilangan prima.

Algoritma: Cetak "Ya"

Kebanyakan orang berpikir bahwa algoritma itu benar. Tidak ada bukti yang diketahui, dan sangat mungkin bahwa ada adalah tidak ada bukti.

Algoritma apa pun yang benar tetapi kami tidak tahu berapa lama waktu yang dibutuhkan untuk menjalankannya dapat diubah menjadi suatu algoritma yang berhenti dalam jumlah waktu yang dijamin tetapi kami tidak yakin apakah itu benar.

$n$$n+1$$0$$\log(n)^2$$0$$\sqrt{n}$

$P=NP$