Apakah ada program yang tidak pernah berhenti dan tidak memiliki bukti non-terminasi?

Seperti lubang hitam dalam ilmu komputer. Kita hanya bisa tahu mereka ada tetapi ketika kita memiliki salah satu dari mereka kita tidak akan pernah tahu itu salah satunya.

halting-problem correctness-proof Otakar Molnár López
sumber

Memutuskan masalah penghentian setidaknya sama sulitnya dengan membuktikan teorema (mengingat teorema Anda hanya dapat menulis sebuah program seperti , program berakhir jika dan hanya jika teorema itu benar). Jika tidak ada program seperti itu, itu berarti Anda dapat membuktikan semua teorema, yang diketahui salah.

T

$T$ if T is true then halt else loop forever

Bakuriu

@ Bakuriu: Bagaimana Anda menulis if T is true?

ruakh

@ruakh: Metode tradisionalnya adalahFor each string S in the (countable) universe of possible strings: If S is a syntactically valid proof of T, halt.

Quuxplusone

@Quuxplusone: Ya, tapi itu sepertinya tidak cocok dengan konstruksi Bakuriu. . .

ruakh

Ini menarik, tetapi di luar sepengetahuan saya. Bisakah Anda menguraikannya?

Evorlor

Jawaban:

Memang ada program seperti ini. Untuk membuktikan ini, anggaplah sebaliknya bahwa untuk setiap mesin yang tidak berhenti, ada bukti yang tidak berhenti.

Bukti-bukti ini adalah string dengan panjang hingga, jadi kami dapat menghitung semua bukti dengan panjang kurang dari untuk beberapa bilangan bulat . $s$ $s$

Kami kemudian dapat menggunakan ini untuk memecahkan masalah penghentian sebagai berikut: Diberikan Mesin Turing dan input , kami menggunakan algoritma berikut: $M$ $x$

s := 0
while (True)
    test if machine M halts on input x in s steps
    look at all proofs of length s and see if they prove M doesn't halt on input x
    set s := s + 1

Jika perhentian pada input , maka perhentian dalam beberapa jumlah terbatas langkah , sehingga Menghentikan algoritma kami. $M$ $x$ $s$

Jika tidak berhenti pada input , maka dengan asumsi kami, ada beberapa panjang bukti mana ada bukti bahwa tidak berhenti. Jadi dalam hal ini, algoritme kami selalu berakhir. $M$ $x$ $s$ $M$

Dengan demikian, kami memiliki algoritme yang memutuskan masalah Berhenti yang selalu berakhir. Tapi kami tahu ini tidak bisa ada, jadi asumsi kami bahwa selalu ada bukti tidak berhenti harus salah.

Ya ampun
sumber

Saya pikir bentuk yang lebih lemah dari teorema ketidaklengkapan godel mengikuti dari ini juga. Pada dasarnya ada hal-hal yang benar tetapi tidak dapat dibuktikan. Ini adalah salah satu eksperimen pemikiran favorit saya yang baru.

Jake

Apakah Anda berpikir mencoba membuktikan P = NP atau mencoba mencari angka sempurna ganjil bisa menjadi salah satu dari program ini?

Otakar Molnár López

Itu tidak masuk akal karena program-program non-terminasi bukan merupakan bukti juga bukan angka tetapi ide yang Anda peroleh telah diangkat. Ada yang mengatakan bahwa PvsNP tidak dapat dibuktikan

Jake

@Jake Saya percaya bagian dari motivasi mesin Turing adalah ekspresi yang lebih bersih dari ide di balik teorema Godel.

cpast

Untuk contoh yang agak lebih konkret, mari kita asumsikan bahwa teori yang kita gunakan untuk bukti kita memiliki fitur-fitur berikut (cukup masuk akal, IMO):

Itu konsisten ; artinya, itu tidak dapat membuktikan kontradiksi.
Rangkaian aksiomanya berulang secara berulang.
Buktinya dapat dituliskan sebagai bitstring yang terbatas.
Pertanyaan apakah string yang diberikan mengkodekan bukti yang terbentuk dengan baik dan benar di dalamnya secara algoritmik dapat ditentukan dalam waktu terbatas.
Cukup ekspresif untuk mengakui bukti teorema ketidaklengkapan kedua Gödel , yang mengatakan bahwa ia tidak dapat membuktikan konsistensinya sendiri.

Dengan asumsi-asumsi itu, program berikut tidak akan pernah berhenti, tetapi tidak dapat dibuktikan (dalam lingkup teori yang kami gunakan) untuk tidak berhenti:

let k := 0;
repeat:
    let k := k + 1;
    let s := binary expansion of k, excluding leading 1 bit;
while s does not encode a proof of a contradiction;
halt.

Detail utama di sini adalah asumsi pertama di atas, yaitu bahwa teori yang kita gunakan untuk bukti kita konsisten. Jelas, kita perlu mengasumsikan ini, agar bukti kita bernilai apa pun, tetapi teorema ketidaklengkapan Gödel yang kedua mengatakan bahwa, untuk teori aksiomatif yang ekspresif dan efektif secara wajar, kita tidak dapat benar-benar membuktikan ini (kecuali mungkin dalam beberapa teori lain , yang konsistensinya kita kemudian perlu berasumsi, dll. dll).

Ilmari Karonen
sumber