Menghentikan masalah - satu masalah yang mengganggu saya

Sepengetahuan saya, menghentikan masalah bertanya apakah ada program yang memutuskan apakah suatu program sedang diuji, diberi beberapa data input (tidak peduli program apa itu, atau data input apa yang kami berikan) akan berakhir atau tidak. Jawaban untuk masalah ini adalah 'tidak'. Dengan kata lain, tidak ada program 'tunggal' yang dapat memverifikasinya untuk semua pasangan yang memungkinkan (beberapa algoritma, beberapa data input).

Tapi itu tidak berarti kita tidak bisa memutuskan apakah tertentu Program X akan menghentikan atau tidak.

Saya belum bisa mengomentari jawaban lain, tetapi salah satunya menarik perhatian saya:

Dalam istilah praktis, ini penting karena memungkinkan Anda memberi tahu atasan Anda yang bodoh "apa yang Anda minta secara matematis tidak mungkin".

Mungkin Anda bisa memberi tahu saya apa yang dimaksud orang itu? Dalam skenario saya, atasan saya yang bodoh dapat meminta saya untuk memverifikasi (sebenarnya, membuktikan atau membantah) apakah program saya (itu adalah program tertentu) akan berakhir atau tidak. Dan tentu saja ada pasangan (algoritma, input data) yang dapat dibuktikan untuk mengakhiri (atau tidak pernah mengakhiri).

Pertanyaannya adalah - dapatkah saya membuktikannya untuk setiap pasangan (program, input data) secara terpisah? Bahkan jika jawabannya adalah ya, maka ada masalah - mungkin ada banyak 'data input'. Jadi cukup wajar untuk bertanya - dapatkah saya membuktikan, untuk setiap algoritma, bahwa algoritma ini akan berakhir (atau sebaliknya), tidak peduli input data apa yang saya berikan?

computability halting-problem pengguna4205580
sumber

Apakah kita dapat menemukan semua bukti semacam itu adalah masalah logika, saya kira, tetapi tentu saja ada banyak yang belum kita temukan .

Raphael

masalah penghentian didefinisikan sebagai suatu algoritma spesifik yang dapat menentukan apakah suatu program akan berhenti atau tidak. Memeriksa program tertentu (atau bahkan beberapa program spesifik) dengan algoritme yang berbeda apakah mereka dapat berhenti atau tidak dapat dilakukan (kasus umum tidak)

Nikos M.

Jawaban:

Tidak, Anda tidak dapat membuktikan ini untuk setiap algoritma (mesin Turing). Ini menjadi pertanyaan tentang sifat bukti daripada pertanyaan tentang perhitungan.

Pertimbangkan mesin Turing berikut : periksa apakah ada bukti untuk pernyataan berhenti, panjangnya(untuk penjelasan tentang referensi diri, lihat teorema rekursi Klenee). Jika bukti tersebut ditemukan, pergilah ke infinite loop (jika tidak dihentikan). $M(x)$ $\forall x \hspace{1mm} M(x)$ $\le |x|$

Jelas Anda tidak dapat membuktikan berhenti untuk semua , karena jika Anda dapat menemukan bukti panjang , itu tidak akan berhenti untuk semua input ukuran . Selain itu, Anda tidak dapat membuktikan tidak berhenti untuk beberapa , karena ini berarti ada bukti untuk penghentian pada semua input (kontradiksi). Situasi di sini adalah, bahwa jika sistem aksioma kami konsisten, maka berhenti untuk semua , tetapi Anda tidak dapat membuktikannya (artinya Anda dapat membuktikan dalam teori Anda bahwa jika konsisten maka $M(x)$ $x$ $p$ $\ge p$ $M(x)$ $x$ $M$ $M(x)$ $x$ $T$ $T$ $\forall x \hspace{1mm} M(x)$ berhenti, tetapi Anda tidak dapat membuktikannya berhenti tanpa asumsi ini, kecuali jika sistem Anda tidak konsisten).

Ariel
sumber

Ini adalah jawaban untuk 'dapatkah saya membuktikan, untuk setiap algoritma, bahwa algoritma ini akan berakhir (atau sebaliknya), tidak peduli input data apa yang saya berikan?' - hanya untuk memastikan.

user4205580

Iya. Butuh lebih banyak karakter

Ariel

Anda mungkin juga tertarik dengan hasil ketidaklengkapan Godel : pada dasarnya, dalam sistem logis apa pun yang cukup kuat untuk berbicara tentang aritmatika, ada pernyataan yang benar yang tidak dapat dibuktikan.

jmite

M

$M$ Mesin - turing, - inputnya. Kemudian kita jalankan dengan, katakanlah, . Program ini diterjemahkan menjadi: "periksa apakah ada bukti untuk pernyataan: untuk semua M (2) penghentian, panjang ..." Tidak masuk akal untuk mengatakan untuk semua . Atau mungkin itu bukan cara saya melihatnya.

x

$x$

x = 2

$x=2$

2

$2$

\leq 2

$\le 2$

2

$2$

user4205580

Variabel terukur baru, pikirkan sebagai berhenti. (input) hanya muncul sebagai batas pada panjang buktinya.

\forall y M (y)

$\forall y M(y)$

x

$x$

Ariel

Untuk satu program tertentu, tentu saya dapat membuktikan bahwa program tersebut akan berhenti pada semua input: program saya telah "berhenti" sebagai instruksi pertamanya.

Contoh lain: Saya dapat memiliki program spesifik yang merupakan simulator mesin Turing (yaitu mesin Turing universal). Ini menafsirkan inputnya sebagai deskripsi dari mesin Turing, dan simulator mensimulasikan mesin berjalan pada pita kosong. Jadi simulator akan berhenti jika input mesin berhenti, dan akan berjalan selamanya jika input mesin dijalankan selamanya. (Jika input tidak dalam format yang benar untuk menggambarkan mesin Turing, simulator akan berhenti.)

Kita tahu tidak mungkin untuk memutuskan apakah mesin Turing sewenang-wenang berhenti ketika dimulai pada kaset kosong. Jadi untuk mesin simulator spesifik saya, tidak ada algoritma untuk memutuskan apa yang dilakukannya pada input sewenang-wenang.

Saya tidak tahu apakah dua contoh ini membantu.

Tentunya di banyak domain masalah masuk akal untuk dapat membuktikan bahwa program tertentu berakhir. Jika program saya melipatgandakan dua matriks saya berharap dapat membuktikan bahwa tidak ada cara yang bisa berlangsung selamanya.

pengguna42735
sumber

Setidaknya saya bisa mengklarifikasi pertanyaan hipotetis yang diduga ditanyakan oleh bos imajiner yang mengarah pada jawaban ini:

Bisakah Anda mendesain program yang mengambil program lain ini / templat / database query / dll. Yang selalu menentukan apakah itu mengakhiri / menimbulkan pengecualian / kehabisan memori?

Inti dari bukti ketidakmungkinan adalah bahwa tugas seperti itu tidak dapat diselesaikan. Tentu saja sudah menjadi rahasia umum saat ini bahwa tugas seperti itu dapat diperkirakan dengan cukup baik, yaitu dimungkinkan untuk memberikan algoritma yang menentukan apakah suatu program akan menaikkan pengecualian, tetapi kadang-kadang jawaban "mungkin menimbulkan pengecualian" meskipun program tidak dapat melakukannya dalam praktek .

Beberapa di antaranya lebih sulit dilakukan dalam praktiknya, misalnya penghentian lebih sulit untuk dibuktikan daripada tidak adanya pengecualian null pointer untuk "program dunia nyata" (tetapi secara teori setara).

cody
sumber