Algoritma untuk memecahkan "masalah terputus-" Turing

"Alan Turing membuktikan pada tahun 1936 bahwa algoritma umum untuk memecahkan masalah penghentian untuk semua pasangan input-program yang mungkin tidak ada"

Dapatkah saya menemukan algoritma umum untuk menyelesaikan masalah penghentian untuk beberapa pasangan input program yang mungkin?

Dapatkah saya menemukan bahasa pemrograman (atau bahasa), di mana saya untuk setiap jenis program dalam bahasa ini, dapat memutuskan apakah program berakhir atau berjalan selamanya?

Dapatkah saya menemukan algoritma umum untuk menyelesaikan masalah penghentian untuk beberapa pasangan input program yang mungkin?

Ya tentu. Misalnya, Anda dapat menulis algoritme yang mengembalikan "Ya, itu berakhir" untuk setiap program yang tidak mengandung loop atau rekursi dan "Tidak, itu tidak berakhir" untuk program apa pun yang berisi while(true)loop yang pasti akan dicapai dan tidak mengandung pernyataan istirahat, dan "Tak tahu" untuk yang lainnya.

Dapatkah saya menemukan bahasa pemrograman (atau bahasa), di mana saya untuk setiap jenis program dalam bahasa ini, dapat memutuskan apakah program berakhir atau berjalan selamanya?

Tidak jika bahasa itu Turing-lengkap, tidak.

Namun ada bahasa lengkap non-Turing seperti misalnya Coq , Agda atau Microsoft Dafny yang Masalah Pemutusannya dapat ditentukan (dan sebenarnya diputuskan oleh sistem jenisnya masing-masing, menjadikannya bahasa total (mis. Program yang mungkin tidak berakhir tidak akan berhenti). menyusun)).

Saya pikir semua jawaban di sini benar-benar dan benar-benar tidak penting. Jawaban atas pertanyaan adalah: dengan asumsi program ini dimaksudkan untuk berhenti, maka ya Anda sebaiknya dapat menghentikannya. Jika Anda tidak dapat menunjukkannya berhenti dengan mudah maka program harus dianggap sangat buruk ditulis dan ditolak oleh Kontrol Kualitas.

Apakah Anda benar-benar dapat menulis algoritma mesin yang sesuai tergantung pada bahasa pemrograman input dan seberapa ambisius Anda. Ini adalah tujuan desain yang masuk akal untuk bahasa pemrograman untuk membuatnya mudah untuk membuktikan penghentian.

Jika bahasanya adalah C ++ Anda mungkin tidak bisa menulis alat, memang tidak mungkin Anda mendapatkan parser, apalagi membuktikan penghentian. Untuk bahasa terstruktur yang lebih baik, Anda harus dapat menghasilkan bukti, atau setidaknya melakukannya dengan asumsi tertentu: dalam kasus terakhir alat harus menampilkan asumsi-asumsi ini. Pendekatan serupa akan mencakup pernyataan pemutusan hubungan kerja dalam bahasa dan menggunakannya dalam situasi kompleks di mana alat akan mempercayai pernyataan tersebut.

Intinya adalah bahwa tidak seorang pun tampaknya memahami bahwa bukti suatu program berhenti memang mungkin karena programmer (baik) yang berniat untuk menulis program penghentian seperti itu selalu melakukannya dengan sengaja dan dengan gambaran mental mengapa mereka berhenti dan bertindak dengan benar: kode semacam itu sengaja dibuat ditulis sehingga jelas bahwa mereka berhenti dan sudah benar dan jika algoritma yang masuk akal tidak dapat membuktikan ini, mungkin dengan beberapa petunjuk, maka program harus ditolak.

Intinya: programmer tidak menulis program yang sewenang-wenang, sehingga tesis tentang teorema berhenti tidak puas dan kesimpulannya tidak berlaku.

pertanyaan yang sangat baik dan (mungkin tidak sengaja dalam). memang ada program pendeteksi penghentian yang dapat berhasil pada set input yang terbatas. ini merupakan area penelitian yang aktif. ini memiliki ikatan yang sangat kuat dengan area pembuktian teorema (otomatis).

Namun ilmu komputer tampaknya tidak memiliki istilah yang tepat untuk "program" yang "kadang-kadang" berhasil. kata "algoritma" biasanya disediakan untuk program yang selalu berhenti.

konsep ini tampaknya berbeda dari algoritma probabilistik di mana teoretikus CS menegaskan ada beberapa probabilitas yang diketahui atau dapat dihitung pada keberhasilan mereka.

ada istilah semialgoritma yang digunakan kadang-kadang tetapi tampaknya sinonim untuk dihitung berulang atau tidak bisa dihitung.

jadi untuk keperluan di sini, sebut mereka quasialgorithms . konsepnya berbeda dari decidable vs undecidable.

$A$$X$$B$$Y$$X \subset Y$$X$$Y$$B$$A$

dalam CS "hierarki algoritma kuasi" ini tampaknya dipelajari sebagian besar hanya secara informal sejauh ini.

itu muncul dalam penelitian berang-berang yang sibuk [1] dan masalah PCP [2]. sebenarnya serangan komputasi berbasis DNA pada PCP dapat dilihat sebagai quasialgorithm. [3] dan itu terlihat di daerah lain yang sudah dicatat seperti pembuktian teorema [4].

[1] Serangan milenium baru pada masalah berang-berang yang sibuk

[2] Mengatasi masalah korespondensi Kiriman oleh Zhao (v2?)

[3] Menggunakan DNA untuk menyelesaikan Masalah Pasca Korespondensi Terikat oleh Kari et al

[4] membuktikan penghentian program oleh Cook et al, Comm. dari ACM

(jadi ini sebenarnya adalah pertanyaan yang sangat mendalam yang layak diterima di TCS.SE imho ... mungkin seseorang dapat bertanya kembali di sana dengan cara yang sesuai & tetap)

Selama bahasa pemrograman yang dipermasalahkan cukup kompleks (yaitu jika Turing selesai), maka selalu ada program dalam bahasa yang tidak dapat diputus oleh program apa pun.

Karena semua kecuali bahasa yang paling primitif adalah Turing lengkap (hanya membutuhkan sesuatu seperti variabel dan kondisional), Anda benar-benar hanya dapat membangun bahasa mainan yang sangat kecil yang dapat Anda selesaikan dengan masalah penghentian.

Sunting: Sehubungan dengan komentar, izinkan saya menjadi lebih eksplisit: Bahasa apa pun yang mungkin Anda rancang untuk menyelesaikan masalah penghentian harus Turing-tidak lengkap. Ini mengesampingkan bahasa apa pun yang berisi set bahan dasar yang sesuai (misalnya "variabel, kondisional dan lompatan", atau seperti kata @ sepp2k, generik "while" -loop).

Rupanya ada beberapa bahasa "sederhana" praktis seperti itu (misalnya pemecah teorema seperti Coq dan Agda). Jika mereka memenuhi gagasan Anda tentang "bahasa pemrograman", Anda dapat menyelidiki apakah mereka memenuhi semacam kelengkapan, atau apakah masalah penghentian dapat dipecahkan untuk mereka.

$T$$T$

Ini cukup sepele. Jika kita mengambil gabungan dari setiap himpunan bagian dari penghentian TM dan himpunan bagian dari TM yang tidak berhenti, hasilnya akan menjadi himpunan dari TM yang masalah penghentiannya dapat ditentukan (jalankan kedua mesin secara paralel, jika yang pertama menerima TM berhenti, jika yang kedua menerima maka mesin tidak berhenti). Namun ini tidak akan menyebabkan banyak bahasa yang menarik.

$\mathsf{ALogTime}$$c$$M$

Ya Anda bisa, tetapi saya ragu itu akan berguna. Anda mungkin harus melakukannya dengan analisis kasus dan kemudian Anda hanya dapat mencari kasus yang paling jelas. Misalnya, Anda dapat mengambil file untuk kode while(true){}. Jika file memiliki kode itu, ia tidak akan pernah berakhir ^. Secara lebih umum Anda dapat mengatakan bahwa suatu program tanpa loop atau rekursi akan selalu berakhir dan ada beberapa kasus yang dapat Anda lakukan yang dapat menjamin bahwa suatu program akan atau tidak akan berakhir, tetapi bahkan untuk program menengah sekalipun hal ini akan sangat sulit dan dalam banyak kasus tidak akan bisa memberi Anda jawaban.

tl; dr: Ya, tetapi Anda tidak akan dapat menggunakannya untuk sebagian besar program yang berguna.

^ Ya, secara teknis jika kode itu tidak ada di jalur-kode atau ada utas lain yang masih bisa dihentikan, tapi saya membuat poin umum di sini.