Mengapa, benar-benar, Masalah Pemutusan begitu penting?


149

Saya tidak mengerti mengapa Masalah Pemutusan sering digunakan untuk mengabaikan kemungkinan menentukan apakah suatu program terhenti. Wikipedia [artikel] [1] dengan benar menjelaskan bahwa mesin deterministik dengan memori yang terbatas akan menghentikan atau mengulangi keadaan sebelumnya. Anda dapat menggunakan algoritme yang mendeteksi apakah daftar yang ditautkan loop untuk mengimplementasikan Fungsi Pemutusan dengan kompleksitas ruang O (1).

Tampak bagi saya bahwa bukti Masalah terputus-putus tidak lebih dari apa yang disebut "paradoks," sebuah kontradiksi referensi diri (paling tidak siklus) dengan cara yang sama dengan paradoks Liar. Satu-satunya kesimpulan yang dibuatnya adalah bahwa Fungsi Menghentikan rentan terhadap pertanyaan cacat tersebut.

Jadi, tidak termasuk program paradoksal, Fungsi Halting dapat dipilih. Jadi mengapa kita menganggapnya sebagai bukti yang bertentangan?

4 tahun kemudian : Ketika saya menulis ini, saya baru saja menonton video ini . Seorang programmer mendapatkan beberapa program, harus menentukan mana yang berakhir, dan video berlanjut untuk menjelaskan mengapa itu tidak mungkin. Saya merasa frustrasi, karena saya tahu bahwa dengan memberikan beberapa program yang sewenang-wenang, ada kemungkinan protagonis dapat membuktikan apakah mereka berakhir. Konsep umum hilang entah bagaimana. Perbedaan antara mengatakan "beberapa program tidak dapat dibuktikan untuk dihentikan," dan, "tidak ada program yang dapat dibuktikan untuk berakhir." Banyak algoritma secara resmi ditunjukkan untuk melakukannya. Kegagalan untuk membuat perbedaan ini, oleh setiap referensi tunggal yang saya temukan secara online, adalah bagaimana saya sampai pada judul untuk pertanyaan ini. Untuk alasan ini, saya sangat menghargai jawabannya yang mendefinisikan kembali fungsi penghentian sebagai terner daripada boolean.


16
"mesin deterministik dengan memori terbatas" adalah "membosankan" karena itu tidak lebih dari robot terbatas; ini tidak berguna untuk memodelkan perhitungan secara umum. Adapun masalah penghentian: itu adalah contoh khusus untuk fungsi yang tidak dapat dihitung (Turing). Jika Anda puas dengan bukti yang tidak konstruktif, Anda tidak "membutuhkannya". Meskipun demikian, masih memiliki relevansi historis.
Raphael

16
Karena itu, pertanyaan Anda dianggap kurang informasi. Anda mungkin ingin memoles dasar-dasar teori komputabilitas Anda (yang akan menantang intuisi Anda yang diinformasikan oleh kenyataan, bukan model yang dibahas di sana). Lihat pertanyaan referensi kami sebagai permulaan. Jika Anda memerlukan "bukti" lebih lanjut bahwa intuisi Anda (sejauh teori berjalan) cacat fatal, baca pertanyaan ini .
Raphael

12
"Anda dapat menggunakan algoritme yang mendeteksi apakah loop daftar tertaut untuk mengimplementasikan Fungsi Henti dengan kompleksitas ruang O (1)" - tetapi jika Anda ingin menyelesaikan masalah untuk komputer dengan penyimpanan 2 GB, Anda akan memerlukan lebih dari 2 ^ 2000000000 langkah dan komputer yang lebih besar.
user2357112

11
Beberapa waktu yang lalu saya mengobrol dengan seorang teman tentang masalah penghentian dan seseorang yang duduk di dekatnya bertanya "apa masalah penghentian itu, apakah itu penting?" dan teman saya menoleh kepadanya dan berkata "jika kita dapat memecahkan masalah yang terhenti, kita dapat membangun kota di atas awan". Ini benar.
Francis Davey

8
@emory Klaim ini kosong benar: P => Qbenar untuk Q apa ??pun, jika kita tahu itu Psalah (dan kita tahu bahwa Masalah Pemutusan tidak dapat dipecahkan). Francis bisa saja berkata, "Jika kita bisa menyelesaikan masalah yang tersendat-sendat, kita bisa menemukan obat untuk kematian itu sendiri". Begitulah implikasi logis didefinisikan.
amalloy

Jawaban:


217

Karena banyak masalah yang sangat praktis adalah masalah yang tersendat. Sebuah solusi bagi mereka untuk memecahkan masalah penghentian.

Anda menginginkan kompiler yang menemukan kode mesin tercepat yang mungkin untuk program tertentu? Sebenarnya masalah penghentian.

Anda memiliki JavaScript, dengan beberapa variabel di tingkat keamanan tinggi, dan beberapa di tingkat keamanan rendah. Anda ingin memastikan bahwa penyerang tidak bisa mendapatkan informasi keamanan yang tinggi. Ini juga masalah penghentian.

Anda memiliki pengurai untuk bahasa pemrograman Anda. Anda mengubahnya, tetapi Anda ingin memastikan itu masih mem-parsing semua program yang dulu. Sebenarnya masalah penghentian.

Anda memiliki program anti-virus, dan Anda ingin melihat apakah itu pernah menjalankan instruksi jahat. Sebenarnya hanya masalah penghentian.

Adapun contoh wikipedia, ya, Anda bisa memodelkan komputer modern sebagai mesin negara-terbatas. Tapi ada dua masalah dengan ini.

  1. Setiap komputer akan menjadi otomat yang berbeda, tergantung pada jumlah bit RAM yang tepat. Jadi ini tidak berguna untuk memeriksa bagian kode tertentu, karena otomat tergantung pada mesin yang dapat dijalankannya.

  2. Anda membutuhkan status jika Anda memiliki n bit RAM. Jadi untuk komputer 8GB modern Anda, itu . Ini adalah angka yang sangat besar sehingga wolfram alpha bahkan tidak tahu bagaimana menafsirkannya. Ketika saya melakukan ia mengatakan bahwa ia memiliki angka desimal. Ini jelas terlalu besar untuk disimpan di komputer biasa.2 32000000000 2 10 9 3000000002n2320000000002109300000000

Masalah Penghentian memungkinkan kita beralasan tentang kesulitan relatif dari algoritma. Ini memberi tahu kami bahwa, ada beberapa algoritme yang tidak ada, yang kadang-kadang, yang bisa kami lakukan hanyalah menebak masalah, dan tidak pernah tahu apakah kami telah menyelesaikannya.

Jika kita tidak memiliki masalah penghentian, kita masih akan mencari algoritma ajaib Hilbert yang memasukkan teorema dan output apakah itu benar atau tidak. Sekarang kita tahu bahwa kita dapat berhenti mencari, dan kita dapat berupaya untuk menemukan heuristik dan metode terbaik kedua untuk memecahkan masalah ini.

UPDATE: Hanya untuk mengatasi beberapa masalah yang diangkat dalam komentar.

@Tyler Fleming Cloutier: Masalah "tidak masuk akal" muncul dalam bukti bahwa masalah penghentian tidak dapat diputuskan, tetapi apa yang menjadi inti dari ketidakpastian adalah benar-benar memiliki ruang pencarian yang tak terbatas. Anda sedang mencari objek dengan properti yang diberikan, dan jika tidak ada, tidak ada cara untuk mengetahui kapan Anda selesai.

Kesulitan masalah bisa terkait dengan jumlah bilangan yang dimilikinya. Mencoba menunjukkan bahwa ada ( ) objek dengan properti sewenang-wenang, Anda harus mencari sampai Anda menemukannya. Jika tidak ada, tidak ada cara (secara umum) untuk mengetahui hal ini. Membuktikan bahwa semua objek ( ) memiliki properti sulit, tetapi Anda dapat mencari objek tanpa properti untuk membuktikannya. Semakin banyak pergantian antara forall dan exist, semakin sulit suatu masalah.???

Untuk lebih lanjut tentang ini, lihat Hirarki Aritmatika . Apa pun di atas tidak dapat ditentukan, meskipun level 1 semi-decidable.Σ00=Π00

Mungkin juga untuk menunjukkan bahwa ada masalah yang tidak dapat diputuskan tanpa menggunakan paradoks yang tidak masuk akal seperti masalah Putting atau Liars paradox. Mesin Turing dapat dikodekan menggunakan string bit, yaitu integer. Tetapi masalah dapat dikodekan sebagai bahasa, yaitu subset dari bilangan bulat. Diketahui bahwa tidak ada ikatan antara himpunan bilangan bulat dan himpunan semua himpunan bagian bilangan bulat. Jadi pasti ada beberapa masalah (bahasa) yang tidak memiliki mesin Turing terkait (algoritma).

@ Bos: ya, ini mengakui bahwa ini dapat dipilih untuk komputer modern. Tapi itu layak untuk mesin tertentu. Jika Anda menambahkan drive USB dengan ruang disk, atau kemampuan untuk menyimpan di jaringan, atau apa pun, maka mesin telah berubah dan hasilnya masih tidak berlaku.

Itu juga harus dikatakan bahwa akan ada banyak kali di mana algoritma mengatakan "kode ini akan berhenti" karena kode akan gagal dan kehabisan memori, dan bahwa menambahkan sedikit memori tambahan akan menyebabkan kode untuk berhasil dan memberikan hasil yang berbeda.

Masalahnya, mesin Turing tidak memiliki jumlah memori yang tak terbatas. Tidak pernah ada waktu di mana jumlah simbol yang tak terbatas ditulis untuk rekaman itu. Alih-alih, mesin Turing memiliki memori "tidak terbatas", artinya Anda dapat terus mendapatkan lebih banyak sumber memori saat Anda membutuhkannya. Komputer seperti ini. Anda dapat menambahkan RAM, atau stik USB, atau hard drive, atau penyimpanan jaringan. Ya, Anda kehabisan memori ketika Anda kehabisan atom di alam semesta. Tetapi memiliki memori tanpa batas adalah model yang jauh lebih berguna.


4
@Mehrdad Untuk definisi yang masuk akal tentang "kode mesin tercepat yang mungkin untuk program tertentu", pertanyaannya masuk akal dan jawabannya adalah "Tidak ada kompiler seperti itu."
David Richerby

13
Ia juga berfungsi untuk menemukan kode mesin terpendek yang mungkin untuk dikeluarkan, kode mesin dengan memori paling sedikit, dll. Untuk program umum, menemukan setiap transformasi optimal tidak dapat ditentukan. Ini pada dasarnya adalah teorema Rice.
jmite

4
Sebagai akibat dari pokok permasalahan tentang masih mencari algoritma magis Hilbert, tanpa konsep yang berkaitan erat dengan Turing equivalence, kami masih akan berdebat tentang apakah goto atau kode modifikasi diri memungkinkan untuk perhitungan yang lebih kuat, mencari bentuk perangkat keras yang lebih kuat dari komputasi , dan argumen yang merupakan bahasa pemrograman terbaik akan jauh lebih subyektif bahkan dari sekarang.
sdenham

3
Bahkan muncul di tempat yang tidak Anda harapkan. Ingin menulis kompiler C ++ yang menolak semua program yang tidak valid sambil mengkompilasi semua yang valid? Selesaikan masalah penghentian terlebih dahulu - C ++ template metaprogramming sudah selesai-Turing, jadi memberi tahu apakah templat Anda valid atau tidak dalam kasus umum perlu diselesaikan.
Markus

7
@Merhrdad: Contoh Anda "mensimulasikan seluruh program komputer" adalah contoh yang sangat baik mengapa masalah penghentian sangat penting. Untuk beberapa program, mensimulasikan program tidak semudah kelihatannya (misalnya, lihat halaman wikipedia tentang penghentian). Jika masalahnya bisa menipu dalam bentuk ini, Anda dapat membayangkan betapa sulitnya menjelaskan kepada seseorang bentuk yang lebih tersembunyi (seperti masalah anti-virus)
Cort Ammon

49

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

Masalah penghentian dan berbagai masalah NP-lengkap (misalnya masalah salesman keliling) muncul banyak dalam bentuk "Mengapa Anda tidak bisa hanya membuat program yang melakukan X?", Dan Anda harus dapat memberikan penjelasan mengapa itu tidak mungkin atau tidak mungkin dilakukan dalam sisa umur alam semesta.

Perhatikan bahwa mungkin untuk merancang bahasa yang tidak menyelesaikan Turing, sehingga dapat dianalisis, dengan melarang rekursi dan iterasi yang tidak terbatas.




8
adalah mungkin untuk merancang bahasa yang tidak menyelesaikan-Turing : Contoh bahasa lengkap yang tidak bermanfaat Turing: SQL (sebenarnya SQL yang dipreteli). Kelengkapan Turing akan secara otomatis menambahkan non-terminasi ke bahasa, yang merupakan sesuatu yang Anda mungkin tidak inginkan ketika menjalankan permintaan db. (Meskipun, saya khawatir semua implementasi SQL modern menawarkan kelengkapan-turing)
Bakuriu

8
@FranciscoPresencia: mereka menggunakan tim peneliti, jadi titik umumnya masih berlaku.
RemcoGerlich

4
@ MoooDuck: hal Flickr tidak memilih antara taman dan burung, itu (upaya untuk) mengkonfirmasi salah satu atau keduanya. ATAU, bukan XOR.
rickster

45

Anda dapat menggunakan algoritme yang mendeteksi apakah daftar yang ditautkan loop untuk mengimplementasikan Fungsi Pemutusan dengan kompleksitas ruang O (1).

Untuk melakukan itu, Anda perlu menyimpan setidaknya dua salinan dari status sebagian program dalam memori, ditambah overhead program pemeriksaan. Jadi pada komputer tertentu, Anda tidak dapat menguji semua program yang dapat dijalankan di komputer itu, hanya program yang dijalankan pada komputer yang lebih kecil dengan memori kurang dari setengahnya.

Masalah penghentian untuk komputer ukuran hingga tertentu tidak dapat diselesaikan pada komputer berukuran hingga itu . Itu hanya dapat diselesaikan pada komputer yang lebih besar. (Ini berlaku untuk metode apa pun, bukan hanya yang Anda usulkan. Saya tidak akan memberikan bukti formal, tetapi inilah intinya. Jika komputer C dapat menjalankan N program yang berbeda yang setidaknya satu P tidak diakhiri , maka komputer V yang dapat menguji apakah program N ini berhenti harus dapat menjalankan program verifikasi N yang berbeda juga. Jika C dan V adalah komputer yang sama, maka P bukan salah satu dari N program berbeda yang dijalankan oleh V, jadi komputer harus menjalankan setidaknya N + 1 program yang berbeda, yang bertentangan dengan asumsi bahwa C menjalankan N program yang berbeda.)

Selain itu, Anda tidak bisa hanya menggunakan algoritme untuk mendeteksi lingkaran dalam daftar tertaut. Anda perlu tahu kapan harus berhenti. Anda dapat berhenti setelah Anda menjalankan langkah-langkah sebanyak yang ada di komputer. Jika suatu program menggunakan hingga bit memori, maka ia dapat memiliki status yang berbeda. Ini sangat cepat menjadi tidak mungkin. Sebagai contoh, komputer biasa mengeksekusi pada urutan satu miliar instruksi per detik; satu miliar detik sedikit lebih dari 30 tahun. Jadi jika Anda menjalankan komputer selama 8 tahun, Anda dapat menguji apakah satu program dengan sekitar 250 juta negara potensial terhenti. Tapi itu hanya menyatakan, yaitu Anda hanya dapat menguji program yang bekerja dalam 7 byte memori.2 M 2 56M2M256

Angka-angka di sana menggambarkan bahwa memikirkan komputer sebagai mesin negara-terbatas jarang praktis. Jumlah negara mungkin terbatas, tetapi sangat membingungkan, tidak praktis. Satu-satunya cara untuk beralasan tentang program non-mainan adalah secara abstrak, bukan dengan menyebutkan keadaan tetapi melalui penalaran logis.

Jadi tidak termasuk program paradoksal, Masalah yang Henti-hentinya dapat ditentukan

Paradoks tidak datang dari masalah, tetapi dari upaya mencari solusi. Untuk setiap program yang diberikan, ada algoritma yang mengatakan "ya" jika program berakhir, dan "tidak" jika program tidak berakhir. Itu sepele: bisa print "yes"atau print "no"tidak. Masalahnya adalah menentukan yang mana yang harus dihubungi. Ketidakmungkinan memecahkan masalah penghentian berarti bahwa tidak ada algoritma untuk membuat penentuan ini. Alasan buktinya menggunakan argumen diagonalisasi adalah karena ia perlu menunjukkan bahwa tidaksolusi bekerja; untuk melakukan itu, itu dimulai dari solusi yang diakui sewenang-wenang, dan menunjukkan bahwa ia harus kehilangan beberapa program dengan membangun program yang terlewat. Diagonalisasi (apa yang Anda sebut "paradoks") secara tidak tepat adalah dalam konstruksi, bukan dalam program yang dihasilkan. Program yang dihasilkan tidak merujuk pada diri sendiri.

Ada hasil yang lebih umum yang disebut teorema Rice yang menyatakan bahwa setiap properti non-sepeleprogram tidak dapat diputuskan - properti apa pun yang hanya bergantung pada perilaku program dan tidak dengan cara yang spesifik seperti yang tertulis (misalnya, "apakah kode sumber terdiri dari kurang dari 42 karakter?" jelas dapat dipilih, sedangkan "apakah ada program yang kode sumbernya terdiri dari kurang dari 42 karakter dan yang mengembalikan hasil yang sama untuk semua input? "bukan, juga" apakah program ini pernah menghasilkan sesuatu? "). Menghentikan hanyalah satu contoh. Ini penting karena sering muncul dalam praktik (biasanya, kami ingin tahu apakah suatu program akan mengembalikan hasil dalam waktu yang wajar mengingat sumber daya terbatas dari komputer yang sedang berjalan, tetapi karena ini jarang bisa dijawab secara praktis, kami bersedia menerima pertanyaan yang lebih sederhana, apakah program pada akhirnya akan berakhir dengan waktu dan memori yang cukup).


2
Saya akan berpikir bahwa pertanyaan "apakah ada program yang akan menghasilkan output yang sama dengan program mandiri (tidak ada input tetapi program itu sendiri), tetapi dalam waktu yang lebih singkat, termasuk waktu untuk memuat program ?" akan dapat ditentukan, meskipun tidak dapat dilaksanakan, karena panjang maksimum dari program kandidat akan dibatasi, seperti juga waktu untuk menguji masing-masing.
supercat

@supercat Ya, properti ini dapat dipilih. Itu tidak dapat ditentukan untuk kasus umum dari suatu program yang mengambil input.
Gilles

1
Saya mendapat kesan bahwa Masalah Pemutusan biasanya mengasumsikan bahwa semua input yang akan diterima suatu program dalam pelaksanaannya digabungkan dengan program tersebut. Jika salah satu memiliki mesin yang ajaib bisa memecahkan Masalah yang terputus-putus untuk program makan setiap tertentu urutan input, bisa seperti mesin menentukan apakah suatu program akan menghentikan untuk semua masukan dibatasi panjang?
supercat

3
@supercat Tidak, oracle halt-untuk-semua-input akan selangkah lebih maju daripada oracle halt-untuk-input-diberikan. Itu akan menjadi pertanyaan yang bagus untuk situs ini ... pada kenyataannya kita memilikinya . Omong-omong, model mental default saya adalah fungsi rekursif, di mana "input" berarti "argumen" dan menjalankan program berarti menerapkannya pada argumen; Anda benar bahwa pernyataan saya salah dalam konteks tentang mesin Turing, saya akan memperbaruinya.
Gilles

28

Tampak bagi saya bahwa Masalah Pemutusan tidak lebih dari apa yang disebut "paradoks," sebuah kontradiksi referensi diri (paling tidak siklus) dengan cara yang sama dengan paradoks Liar. Satu-satunya kesimpulan yang dibuatnya adalah bahwa Fungsi Menghentikan rentan terhadap pertanyaan cacat tersebut

Tidak, bukan itu masalah penghentiannya. Paradoks seperti paradoks pembohong tidak benar atau salah, mereka tidak masuk akal. Algoritma deterministik di sisi lain akan berhenti untuk input yang diberikan atau akan berjalan selamanya. Fungsi ini halts(program, input)memiliki nilai deterministik yang terdefinisi dengan sempurna untuk setiap program, untuk setiap input. Kami tidak bisa memutuskannya untuk program apa pun. Atau, lebih tepatnya: Kami tidak dapat menulis program yang dapat memutuskannya untuk setiap pasangan program / input.

Contoh yang serupa (mungkin kurang abstrak) adalah fungsi , yang secara intuitif didefinisikan sebagai Urutan terpanjang dari 1 mesin Turing dengan status , dimulai dengan pita kosong, dapat menulis sebelum berakhir. Untuk setiap , hanya ada sejumlah mesin Turing terbatas, dan masing-masing dari mereka berakhir pada titik tertentu (maka Anda dapat menghitung jumlah mesin), atau berjalan selamanya (kemudian berang-berang yang sibuk tidak peduli tentang hal itu - itu hanya melihat program yang berakhir). Jadi, fungsi berang-berang yang sibuk memiliki nilai deterministik untuk setiap . (Kami bahkan tahu itu untuk beberapa keciln n n n Σ ( n )Σ(n):=nnnn, karena kita dapat melihat setiap program dan menemukan bukti mengapa mereka tidak akan pernah berhenti.) Tetapi tidak ada program yang menghitung .Σ(n)


2
Perlu dicatat bahwa dalam bentuk umum Paradox Liar membuat referensi eksplisit untuk dirinya sendiri, tetapi masalah yang sama dapat muncul bahkan jika tidak. Apakah jawaban atas pernyataan itu terbentuk dengan mengambil teks, "Apakah jawaban atas pernyataan itu terbentuk dengan mengambil teks, dan memasukkan setelah koma yang pertama, sebuah salinan terlampir dalam tanda kutip, bukan?" dan memasukkan setelah koma salinan pertama terlampir dalam tanda kutip tunggal, bukan? Pernyataan seperti itu tidak secara eksplisit merujuk pada diri sendiri tetapi merujuk pada kebenaran pernyataan yang identik dengan karakter-untuk-karakter.
supercat

2
@supercat: ya, saya pikir saya belum pernah melihat seekor quine dalam bahasa Inggris sebelumnya ...
SamB

@ SamB: Saya sudah melihat beberapa, tetapi memutuskan untuk mencoba tangan saya pada formulasi asli yang, sementara lebih bertele-tele dari beberapa, membaca (mungkin) lebih alami.
supercat

24

Saya tidak mengerti mengapa Masalah Pemutusan sering digunakan untuk mengabaikan kemungkinan menentukan apakah suatu program terhenti. Artikel Wikipedia dengan benar menjelaskan bahwa mesin deterministik dengan memori yang terbatas akan menghentikan atau mengulangi keadaan sebelumnya. Anda dapat menggunakan algoritme yang mendeteksi apakah daftar yang ditautkan loop untuk mengimplementasikan Fungsi Pemutusan dengan kompleksitas ruang O (1).

Pertama, ya, secara teori masuk akal untuk melihat komputer nyata, yang memiliki memori hingga, sebagai mesin keadaan terbatas. Tetapi dalam praktiknya jumlah keadaan komputer nyata sangat besar, sehingga komputer nyata jauh lebih baik dimodelkan oleh mesin Turing atau model komputasi keadaan tak terbatas lainnya.

Dan kedua, bahkan secara teoritis masuk akal untuk melihat komputer modern sebagai mesin negara tanpa batas. Mesin Turing tidak memiliki pita tak terbatas, ia memiliki pita yang selalu dapat diperpanjang ketika mesin kehabisan memori. Dan bukankah itu tepatnya yang dapat kita lakukan dengan komputer sungguhan? (Dan jika ruang alamat CPU habis, kita dapat menggunakan cloud, dll.)

Tampak bagi saya bahwa Masalah Pemutusan tidak lebih dari apa yang disebut "paradoks," sebuah kontradiksi referensi diri (paling tidak siklus) dengan cara yang sama dengan paradoks Liar. Satu-satunya kesimpulan yang dibuatnya adalah bahwa Fungsi Menghentikan rentan terhadap pertanyaan cacat tersebut. Jadi tidak termasuk program paradoksal, Masalah yang Henti-hentinya dapat ditentukan. Jadi mengapa kita menganggapnya sebagai bukti yang bertentangan?

Ada perbedaan antara masalah penghentian dan bukti dari keraguannya. Masalah penghentian hanyalah spesifikasi untuk program : sebagai input program mendapatkan kode sumber program dan input , dan program harus mengembalikan true jika berhenti pada input dan false jika tidak. Ini adalah spesifikasi yang sangat jelas; tidak ada yang paradoksal tentang hal itu: setiap pasangan kode sumber dan input memiliki satu jawaban benar yang jelas.P x H P xHPxHPx

Bukti Turing tentang ketidakpastian masalah penghentian menggunakan trik yang mirip dengan paradoks Liar, ya. Paradoks sering didefinisikan sebagai kontradiksi yang nyata , dan beberapa orang menyimpulkan bahwa paradoks bukanlah kontradiksi nyata . Namun, paradoks Russel (set-theoretic set formal counterpart untuk pembohong's paradoks) menunjukkan kontradiksi nyata dalam matematika, dan bukti keraguan tentang masalah penghentian menggunakan kontradiksi nyata untuk pembuktiannya oleh kontradiksi.


1
+1 untuk menjelaskan hubungan antara komputer nyata, mesin negara hingga dan mesin Turing yang merupakan bagian penting dari pengaturan pertanyaan.
David Richerby

1
Anda telah menggelitik minat saya. Apa perbedaan antara kontradiksi nyata dan kontradiksi nyata?
Brent

Cara lain untuk menyatakan hal ini: secara umum, pemrograman tidak mengasumsikan sumber daya yang terbatas. Sebagian besar algoritma yang kami desain atau program yang kami tulis tidak ditulis untuk menggunakan jumlah sumber daya komputasi yang terbatas, atau bahkan tetap, kecuali jika kami secara khusus merancang mereka yang cara (misalnya ini sering diperlukan saat pemrograman untuk sistem embedded).
reinierpost

3
@ Bos. Banyak paradoks yang tidak bertentangan sama sekali, tetapi hanya pada pandangan pertama. Ketika kita melihat lebih dekat, ternyata ada kesalahan dalam penalaran, atau beberapa kata yang artinya sedikit berubah dengan menggunakannya dalam konteks yang berbeda, atau sesuatu yang serupa. Namun, kadang-kadang, sebuah paradoks mengungkap kontradiksi nyata.
Hoopje

Saya telah mempelajari masalah ini sejak dan sejak OP saya. Apakah teorema ketidaklengkapan G?del menyiratkan bahwa selalu mungkin untuk menghasilkan beberapa paradoks terlepas dari sistem logika yang digunakan?
Brent

17

jmite telah menjawab pertanyaan dengan sangat baik. Izinkan saya menambahkan catatan kecil tentang kesamaan yang dirasakan dengan "Paradox Liar" yang saya pikir disebabkan oleh penggunaan mekanisme referensi-diri.

Referensi-diri tidak paradoks!

Referensi diri adalah alat yang sangat berguna dalam perhitungan (bahwa suatu algoritma dapat merujuk pada kode, refleksi ) dan bahasa manusia (yang dapat kita rujuk pada diri kita sendiri, kesadaran diri ).

Masalah yang menyebabkan Paradox Liar bukan referensi-diri, ia mencoba menggunakan predikat kebenaran untuk bahasa (formal) di dalam bahasa. Ini akan menyebabkan masalah bahkan tanpa referensi-diri, kita tidak perlu kemampuan untuk menggunakan referensi-diri untuk mendapatkan paradoks: referensi-diri dapat dihilangkan! . Itu hanya akan membuat kalimatnya kurang bagus dan ringkas tetapi tidak sulit untuk dilakukan. Ini pada dasarnya bagaimana teorema Fixed Point Kleene terbukti. Apa yang disiratkan oleh Paradox Liar adalah bahwa kebenaran pernyataan dalam bahasa (formal) adalah transendental ke bahasa itu, bukan bahwa referensi diri itu bermasalah.


Tampak bagi saya bahwa ketidaknyamanan Anda bukan karena ketidakpastian masalah penghentian (untuk mesin Turing) tetapi dengan penerimaan mesin Turing sebagai model teoritis untuk komputer. Biasanya (meskipun tidak selalu) mesin Turing (dan model komputasi yang setara seperti Random Access Machines ) sangat berguna untuk diskusi perhitungan pada komputer yang sebenarnya daripada finata automata dan ada alasan bagus untuk itu (perlu diingat bahwa mesin Turing tidak memiliki jumlah memori yang tak terbatas, ia memiliki jumlah memori yang tidak terbatas dan ini adalah hal-hal yang berbeda: tanpa batas berarti bahwa kami dapat menyediakan mesin dengan lebih banyak memori saat dibutuhkan, bukan menggunakan jumlah memori yang tak terbatas).

Tentu, jika Anda ingin menganggap komputer sebagai automata terbatas, dan itu masuk akal untuk tujuan Anda, maka masalah penghentian untuk automata terbatas dapat ditentukan (dan yang dapat ditentukan artinya adalah decidable dengan mesin Turing, bukan oleh automata terbatas). Namun bukan itu yang biasanya orang maksudkan ketika mereka menggunakan masalah penghentian, mereka berarti masalah penghentian untuk mesin Turing.

s2s


14

masalah berhenti memperkenalkan konsep matematika baru dari "keraguan" yang sebelumnya tidak ada dalam matematika. itu adalah ("tampaknya paradoks") bukti bahwa beberapa masalah tidak memiliki "bukti". ini terhubung dengan konsep Godelian tentang ketidakberlangsungan. Teorema Godels mendahului perumusan masalah yang terhenti oleh Turing selama beberapa tahun. Hasil Godels dianggap agak abstrak pada saat itu dan hanya diketahui oleh para peneliti dan spesialis. Formulasi turings menunjukkan bahwa prinsip keraguan dalam kaitannya dengan pertanyaan yang sangat praktis / pragmatis / terapan dalam ilmu komputer seperti menentukan apakah program yang sewenang-wenang berhenti dan dianggap sebagai konsep yang jauh kurang teoretis, muncul dalam tantangan modern seperti (sebuah tantangan apakah komputer dapat menemukan teorema) dan membuktikan penghentian program.

Sudut lain yang menarik adalah bahwa ada beberapa masalah yang sangat lama dalam teori bilangan (Diophantine) yang berasal dari Yunani yang tidak terbukti selama ribuan tahun. ada hasil terkait bahwa pertanyaan umum tentang persamaan Diophantine tidak dapat diputuskan disebut masalah / teorema Hilberts 10 . Hilbert hidup pada pergantian abad ke-20 dan mengusulkan sebagai program penelitian bahwa matematika dapat menemukan pendekatan sistematis untuk masalah matematika. tantangan / rencana ini secara serius dikejutkan oleh penemuan ketidakpastian dari beberapa dekade kemudian. Ketidakpastian terus menjadi bidang penelitian yang sangat maju dan batas antara masalah yang tidak dapat ditentukan dan diputuskan mungkin akan selalu berada di bawah studi dan analisis lebih lanjut.


14

Anda tampaknya membingungkan bukti klasik "self referential" yang mendasari bahwa masalah Hentikan tidak dapat diselesaikan dengan masalah Henti (alias Henti) itu sendiri.

Program referensi-diri itu - program yang berhenti jika dan hanya jika tidak berhenti - dibuat agar mudah untuk membuktikan bahwa Anda tidak dapat menyelesaikan Berhenti. Fakta bahwa kita membuktikan X tidak mungkin melalui teknik Y tidak menyiratkan Y adalah satu-satunya alasan mengapa kita tidak dapat menyelesaikan X.

Dengan kata lain, tidak hanya kita tidak dapat menyelesaikan Menghentikan, kita tidak dapat mendeteksi bahwa suatu program jenis program yang kita tidak dapat menentukan apakah itu Menghentikan, selain ukuran kasar seperti "jika dibutuhkan lebih dari 1 menit untuk berjalan, berpura-pura tidak berhenti ".

Jika Anda mulai dari masalah Penghentian, dan mengurangi masalah lain untuk itu, Anda akhirnya mencapai titik bahwa Anda telah mengurangi hampir setiap pertanyaan tentang program tentang hal itu. Kita berakhir dengan Teorema Rice:

Misalkan S beberapa properti non-sepele 1 apa menerima Turing Machine. Itu berarti ada setidaknya satu Mesin Turing yang menerima input dengan properti S, dan satu yang tidak.

Maka tidak dapat dipastikan jika Turing Machine T yang diberikan menerima input dengan properti S.

Anda ingin tahu apakah Mesin Turing menerima bilangan bulat genap? Tidak dapat ditentukan.

Anda ingin tahu apakah Mesin Turing menerima menerima urutan aritmatika? Tidak dapat ditentukan.

Anda bisa beralasan tentang nyali Turing Machine secara umum. Anda dapat mempertimbangkan tentang Mesin Turing tertentu, dan membuktikan apakah itu akan menghentikan / menerima beberapa urutan / dll. Tetapi Anda tidak bisa tahu apakah teknik Anda akan bekerja pada Mesin Turing berikutnya yang Anda beri makan.


1 Dengan property ofitu tidak termasuk mekanisme bagaimana hal itu diterima - hanya dari apa yang diterima. "Itu menerima dalam 100 langkah atau kurang" adalah properti bagaimana ia menerima, bukan dari apa yang diterima.


Anda mungkin ingin menjelaskan apa itu "properti", karena penafsiran naif yang mungkin dibuat akan salah.
Rick Decker

@ Trik Saya pikir catatan kaki mencakupnya sekarang?
Yakk

7

Anda benar bahwa masalah berhenti seperti yang biasa diperkenalkan dan dinyatakan adalah gotcha belaka. Itu tidak membuktikan bahwa tidak boleh ada fungsi penghentian tiga bernilai ('penghentian', 'pengulangan', 'tidak tahu') yang dalam praktiknya selalu mengembalikan 'penghentian' atau 'pengulangan' dan hanya mengembalikan 'tidak' tidak tahu 'untuk kasus sudut yang dibangun khusus misalnya.

Dua alasan masalah penghentian signifikan:

1) Ini adalah salah satu masalah pertama yang tidak dapat dipastikan. Sekalipun secara hipotetis hanya ada satu yang 'tidak tahu', itu akan tetap menarik secara matematis.

2) Beberapa masalah berkurang menjadi masalah berhenti di mana penyerang jahat dapat memasok kasus untuk dianalisis. Ini memaksa kita untuk menerima bahwa mungkin ada kasus yang valid yang masih harus kita tolak.

Sebagai renungan ke poin kedua, analisis perangkat lunak adalah masalah yang sulit, meskipun banyak kemajuan telah dibuat baik dalam analisis dan dalam desain bahasa sehingga membuat analisis lebih mudah. Jika Anda dapat menunjukkan bahwa tugas tertentu mirip dengan analisis perangkat lunak, ya, sulit dengan huruf kapital H. 'Tidak mungkin karena akan sama dengan menyelesaikan masalah penghentian', meskipun secara teknis salah atau tidak relevan dalam banyak kasus, sering digunakan singkatan untuk pengamatan ini.


5

Ada argumen pelawan yang dikemukakan oleh Eric Hehner dalam serangkaian makalah yang berpendapat bahwa ketidakmampuan memecahkan Masalah Pemutusan Hubungan Kerja umumnya disalahpahami. Koran-koran, "Epimenides, G?del, Turing: Kekusutan Emas Abadi", "Masalah dengan Masalah Pemutusan", "Merekonstruksi Masalah Pemutusan", dan "Masalah Pemutusan", dapat ditemukan di sini . Agar jawaban ini bukan "hanya tautan", saya akan mencoba merangkum salah satu kesimpulannya, tetapi bukan argumennya.

f(0)=1f(0)=2hh(M)MHhh


3
Saya tidak mengikuti. Fungsi penghentian adalah predikat terdefinisi dengan baik dan valid - untuk setiap mesin Turing yang diberikan dan input apa pun yang diberikan, mesin berhenti atau loop. (Anda tidak memiliki referensi yang tepat; papar mana yang Anda rangkum?)
Raphael

@ Raphael Bahwa fungsi didefinisikan dengan baik secara umum diterima sebagai fakta. Pandangan Hehner berbeda dan dijelaskan dalam makalahnya. Saya akan mengedit jawaban saya untuk memberikan nama-nama surat kabar.
Theodore Norvell

Katakan saja bahwa apa pun argumen Hehner adalah [Saya belum membaca makalah] mereka menjadi kontroversial setidaknya dalam bacaan / pendekatan pertama mereka: ' cs.toronto.edu/ ~ hehner / Shallitaffair.pdf
Fizz

Dan itu tidak jelas mengingat sifat dan jumlah kutipan bahwa makalah Hehner (tentang ini) memiliki bacaan tambahan (dari karya-karyanya tentang ini) yang layak untuk direpotkan.
Fizz

Buktinya tampak sangat solid dan menunjukkan bahwa itu hanya pengulangan hal-hal konyol yang dapat Anda lakukan dalam filsafat seperti mencoba menganalisis pernyataan referensial diri berikut untuk kebenarannya: "Kalimat ini salah." yang jika benar berarti itu salah yang berarti itu sebenarnya benar, tidak ada yang membuatnya salah lagi ... jadi ini tampak seperti pertanyaan filosofis yang memandang laut tidak begitu penting. en.wikipedia.org/wiki/Liar_paradox , paradoks penghentian mungkin merupakan kasus para ilmuwan yang tidak berbicara dengan para filsuf.
James Wakefield

3

Saya ingin menawarkan penjelasan yang berbeda tentang pentingnya masalah penghentian yang melibatkan orang daripada mesin.

Ini adalah kuliah terakhir dari kursus Struktur dan Interpretasi MIT 1986 ; profesor bertanya, "Apakah ada pertanyaan?" dan bersiap untuk mengakhiri kuliah, ketika salah satu siswa bertanya: "Apakah ini pertanyaan terakhir?"

Pikirkan sejenak. Bagaimana guru dapat menjawab ini? Jika siswa memutuskan untuk bertentangan dengan guru, tidak ada jawaban yang valid yang dapat diberikan oleh guru - ini seperti masalah penghentian.

Kami terbiasa memikirkan masalah penghentian secara abstrak, menggunakan fungsi dan mesin, tapi jauh lebih dalam dari itu. Pada dasarnya, ini berarti bahwa ada pertanyaan yang benar-benar valid yang tidak dapat dijawab.

PS: Kalau tidak tahu apa yang saya bicarakan, tonton saja, itu luar biasa.


Tetapi jika saya akan mengeksekusi doesHalt(programCode, input);, program tidak bisa tahu apa doesHaltfungsinya kembali. Tidak mungkin bagi program untuk berhenti setelah doesHaltfungsi telah mengevaluasinya.
Tvde1

0

Saya dapat dengan mudah menulis sebuah program yang diberi input n, baik output prima terkecil p> n sehingga p + 2 juga prima, atau berjalan selamanya jika tidak ada p seperti itu. Jika Anda dapat memecahkan masalah untuk memprediksi apakah program saya berhenti untuk setiap input, Anda baru saja menyelesaikan Twin Prime Conjecture.

Sangat mungkin bahwa dugaan ini mungkin terbukti tidak dapat diputuskan, dalam hal ini kita akan memiliki program langsung di mana program penghentian gagal.


Saya pikir Anda mencampur "Turing-diputuskan" dengan gagasan yang sangat berbeda; bahkan, Anda mungkin tersandung ke dalam kesalahan "tua yang sama" secara tidak sengaja. Lihat juga di sini dan di sini .
Raphael
Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.
Judi bola