Menghentikan masalah yang dapat dihitung untuk input / asumsi tertentu

19

Dari pemahaman saya tentang bukti bahwa penghentian masalah tidak dapat dihitung, masalah ini tidak dapat dihitung karena jika kita memiliki program P (x) yang menghitung apakah program x berhenti atau tidak, kita mendapat paradoks ketika memberikan P sebagai input ke P yang sama, memiliki: P (P), mencoba memutuskan apakah P berhenti atau tidak menggunakan P itu sendiri.

Jadi pertanyaan saya adalah: apakah menghentikan masalah dapat dihitung oleh program P untuk semua program lain yang digunakan sebagai input tetapi P itu sendiri? Dengan kata lain: apakah menghentikan masalah tidak hanya dapat dihitung dalam kasus khusus ini atau buktinya lebih umum dan saya kehilangan sesuatu?

halting-problem Alessio Martorana
sumber

Saya pikir Anda salah memahami bukti bahwa masalah penghentian tidak dapat dihitung. P (P) hanya mengembalikan true, karena P selalu menentukan apakah suatu program berhenti dalam waktu yang terbatas. Anda perlu melakukan konstruksi yang sedikit rumit untuk mencapai kontradiksi.

Dan Staley

Saya pikir Anda akan mendapatkan jawaban yang lebih baik dan mungkin secara praktis lebih relevan jika Anda bertanya apakah ada banyak program yang masalah penyelesaiannya dapat diselesaikan. Lagipula, banyak program bahkan dapat diverifikasi secara formal , yang tentunya mencakup penentuan apakah mereka berhenti dengan input yang diberikan. Saya sangat mengira bahwa kelompok itu tidak dapat ditentukan (karena itu akan berarti penyelesaian ..., Anda tahu), tetapi untuk sebagian besar program dunia nyata tidak ada hambatan untuk mengatakan apakah mereka berhenti atau tidak, untuk input yang relevan.

Peter - Pasang kembali Monica

10

Jika adalah fungsi yang dapat dihitung, maka , didefinisikan sebagai $f$ $g$

g (n) = {\begin{cases} f (n) & if n \neq k \\ v & otherwise \end{cases}

$g(n) = \begin{cases} f(n) & \mbox{if } n \neq k \\ v & \mbox{otherwise} \end{cases}$

juga dapat dihitung, untuk pilihan . $k,v$

Pada dasarnya, jika Anda memiliki program yang menghitung untuk semua kecuali untuk , Anda dapat "memperbaiki" kasing itu (misalnya menggunakan a ) dan mendapatkan program lain yang menghitung untuk semua . $P'$ $g(n)$ $n$ $n=k$ if then else $P$ $g(n)$ $n$

Karenanya, jika Anda dapat menghitung fungsi penghentian "kecuali untuk satu kotak", Anda juga dapat menghitung fungsi penghentian (tanpa pengecualian). Dari situ, Anda bisa mendapatkan kontradiksi seperti biasa.

Kesimpulan: tidak, Anda tidak dapat memutuskan masalah penghentian "kecuali satu kasus" (atau "kecuali banyak kasus").

chi
sumber

1

Ok, saya pikir saya mendapatkannya secara matematis ... Tapi saya bertanya-tanya: apakah saya akan mencoba untuk menulis sebuah program yang menghitung HP masalah apa yang akan saya hadapi? Mengapa dan bagaimana pada titik tertentu saya akan mengerti bahwa saya tidak dapat menulis program seperti itu?

Alessio Martorana

@AlessioMartorana Tergantung: bagaimana Anda mendekati masalah seperti itu? Masalah utama adalah bahwa

harus selalu berhenti, bahkan ketika inputnya adalah program yang tidak berhenti - jadi Anda tidak bisa hanya mencoba mensimulasikan program input.

P

$P$

chi

Dan seandainya kita bisa melihat kode program input? Tidak bisakah kita dari kode melihat apakah program berhenti?

Alessio Martorana

2

@AlessioMartorana Kita memang bisa melihat kode, tetapi jika ada misalnya perulangan sementara kita tidak bisa mengatakan banyak secara umum. Suatu loop sementara mungkin memeriksa semua bukti yang mungkin dari dugaan matematika arbitrer, dan berhenti hanya jika bukti ditemukan. Memutuskan apakah loop ini berhenti berarti memutuskan apakah dugaan tersebut dapat dibuktikan. Memecahkan HP akan memberi kita mesin yang akan menjawab Ya (dapat dibuktikan) / Tidak (tidak dapat dibuktikan) untuk pertanyaan matematika formal apa pun. Itu akan sangat kuat dan tidak realistis.

chi

1

@AlessioMartorana Jika Anda berpikir Anda telah menulis sebuah program yang memecahkan HP, di mana program Anda akan gagal ada dalam salah satu dari dua cara: untuk beberapa program mungkin mengembalikan hasil yang salah (mengatakan sesuatu berhenti ketika tidak atau mengatakan sesuatu tidak ' t berhenti ketika itu terjadi) dan / atau program penentu Anda sendiri tidak akan berhenti pada banyak input dengan Anda tidak dapat mengetahui apakah itu benar-benar tidak akan berhenti atau jika hanya perlu lebih banyak waktu untuk menghitung jawabannya.

Shufflepants

21

apakah menghentikan masalah dapat dihitung oleh program P untuk semua program lain yang digunakan sebagai input tetapi P itu sendiri?

Tidak. Pertimbangkan urutan tak terhingga dari program , di mana adalah "Pindahkan kepala $P_1, P_2, \dots$ $P_i$ $i$ kuadrat ke kanan, lalu kuadrat ke kiri, lalu lakukan persis apa yang akan lakukan." Setiap program ini menghasilkan keluaran yang sama persis dengan untuk setiap input (termasuk perulangan selamanya jika berulang selamanya), tetapi semuanya adalah program yang berbeda. $i$ $P$ $P$ $P$

Dan Anda tidak dapat menyiasatinya dengan hanya meminta untuk bekerja pada program yang secara fungsional tidak setara dengan itu sendiri, karena properti itu juga tidak dapat diputuskan. Mungkin masalahnya akan dapat diputuskan ketika terbatas pada contoh-contoh itu (meskipun saya kira itu tidak akan terjadi) tetapi serangkaian contoh tidak dapat diputuskan, sehingga Anda tidak dapat benar-benar melakukan pembatasan. $P$

David Richerby
sumber

15

Saya menduga kalimat terakhir Anda mungkin benar, tetapi saya tidak berpikir itu mengikuti bahwa karena sebuah properti tidak dapat dipastikan yang membatasi set input berdasarkan pada properti itu akan membuat masalah tidak dapat diputuskan. Sebagai contoh bodoh, jika Anda membatasi rangkaian input untuk menghentikan program (properti yang tidak dapat ditentukan), masalahnya akan dapat diputuskan (oleh program yang selalu mengembalikan true).

Owen

3

@Owen Ketika pembatasan itu sendiri tidak dapat dipastikan, Anda tidak dapat memaksakan pembatasan itu sehingga tidak dapat membeli apa pun dalam kenyataan.

David Richerby

5

Ada algoritma untuk menunjukkan bahwa kelas program tertentu melakukan atau tidak berhenti. Sebagai contoh,

Dimungkinkan untuk menentukan secara algoritmik apakah suatu program yang memodelkan mesin kondisi-terbatas berhenti.
Dimungkinkan untuk menentukan secara hitung apakah mesin turing yang terikat linier berhenti
Jika Anda tahu apa kelas kompleksitas suatu program, maka Anda tahu bahwa program berhenti untuk input yang terbatas.

Meskipun tidak ada algoritma untuk menentukan apakah program arbitrer berhenti, sebagian besar kode dirancang untuk berhenti (seperti kebanyakan subrutin) atau tidak berhenti (seperti loop tak terbatas untuk menangani peristiwa), dan dimungkinkan untuk secara algoritmik menentukan mana yang mana. Dengan kata lain, Anda dapat memiliki algoritme yang menjawab "berhenti", "tidak berhenti", atau "Saya tidak tahu", dan algoritme semacam itu dapat dirancang untuk mencakup program yang cukup sehingga berguna.

Antonio Perez
sumber

Apa hubungannya ini dengan goto? Tidak bisakah kita memiliki program yang menggunakan goto dan masih memutuskan apakah akan berhenti, asalkan memodelkan mesin keadaan terbatas?

Bergi

Saya akan menulis tentang menghentikan dalam hal for-loop, dan kemudian mengubahnya hanya untuk berbicara tentang mesin negara yang terbatas dan yang lainnya

Antonio Perez

4

Bukti berdasarkan kontradiksi tidak harus lengkap , satu contoh tandingan saja sudah cukup. Bukti masalah penghentian tidak dapat diputuskan memberi Anda salah satu contoh P yang properti penghentiannya tidak dapat diputuskan. Bukti ini tidak menyatakan bahwa P adalah satu-satunya program seperti itu, pada kenyataannya, mungkin ada bukti independen yang membangun kelas P.

Dmitry Grigoryev
sumber

3

Buktinya memang lebih umum: masalah penghentian adalah kasus khusus teorema Rice , yang menyatakan

$\Phi$

$A$ $B$ $\Phi(A)$ $\Phi(B)$ berlaku.

$x$ $x$ tidak dapat ditentukan; Anda tidak bisa mendapatkan decidability dengan mengurangi ruang input.

Anda bisa mendapatkan beberapa hasil dengan membatasi ruang program yang ingin Anda kerjakan, meskipun pembatasan ini harus cukup drastis. Misalnya, jika Anda dijamin bahwa program Anda diberikan penghentian dalam 100 langkah atau berjalan selamanya, memutuskan apakah penghentiannya menjadi mudah.

$N$ $k$ $BB(k)$

Anton Golov
sumber

1

N

$N$

1

Paragraf terakhir menyerupai Busy Beaver.

Evil

Sehubungan dengan batasan "cukup drastis": bahasa pemrograman total adalah sesuatu. Mereka cenderung membutuhkan tingkat kecanggihan yang relatif tinggi, jadi mungkin Anda menganggapnya drastis, tetapi mungkin untuk memecahkan masalah nyata dalam ruang program yang terbukti terhenti.

Ben Millwood

Memasukkan tautan ke en.wikipedia.org/wiki/Rice%27s_theorem akan membuat IMO masuk akal.

Dmitry Grigoryev

Terima kasih, saya telah memperbarui jawabannya. @ BenMillwood Tentu saja, tetapi memberikan solusi mereka adalah "membuat semuanya berhenti" Saya tidak yakin itu benar-benar apa yang dicari Alessio. Sebuah kasus di mana perilaku penghentian dapat ditentukan tetapi non-sepele akan menarik, meskipun: mungkin Agda + tipe coinductive?

Anton Golov

0

Biarkan R menjadi himpunan enumerable tapi non rekursif rekursif. Ada banyak set seperti itu. Biarkan T menjadi mesin Turing yang berhenti pada input k jika dan hanya jika k ada di R. T seperti itu ada untuk setiap himpunan enumerable rekursif. Tidak mungkin untuk menulis sebuah program yang dapat memecahkan masalah penghentian untuk T. ini. Ini karena algoritma apa pun untuk menentukan apakah T berhenti akan menghasilkan suatu algoritma untuk menentukan keanggotaan dalam R, yang tidak mungkin jika R tidak rekursif. Karena ada banyak R yang tak terhingga, yang masing-masing memberikan mesin Turing yang berbeda, ada banyak mesin Turing yang tak terhingga yang gagal diprogram untuk menghentikan program P.

John Coleman
sumber

Menghentikan masalah yang dapat dihitung untuk input / asumsi tertentu

Jawaban: