Apakah ada himpunan bagian dari program yang menghindari masalah penghentian

Saya baru saja membaca penjelasan lain tentang masalah berhenti, dan itu membuat saya berpikir semua masalah yang saya lihat yang diberikan sebagai contoh melibatkan urutan tak terbatas. Tapi saya tidak pernah menggunakan urutan yang tak terbatas dalam program saya - mereka terlalu lama. Semua aplikasi dunia nyata memiliki batas bawah dan atas. Bahkan real tidak benar-benar real - mereka perkiraan disimpan sebagai 32/64 bit dll.

Jadi pertanyaannya adalah, adakah subset program yang dapat ditentukan jika mereka berhenti? Apakah cukup baik untuk sebagian besar program. Dapatkah saya membangun satu set konstruksi bahasa yang saya dapat menentukan 'haltability' dari suatu program. Saya yakin ini telah dipelajari di suatu tempat sebelumnya sehingga petunjuk apa pun akan dihargai. Bahasa tidak akan turing lengkap, tetapi apakah ada sesuatu yang hampir sempurna selesai yang cukup baik?

Cukup alami konstruksi seperti itu harus mengecualikan rekursi dan tidak terikat saat loop, tapi saya bisa menulis sebuah program tanpa yang cukup mudah.

Membaca dari input standar sebagai contoh harus dibatasi, tetapi itu cukup mudah - saya akan membatasi input saya hingga 10.000.000 karakter dll, tergantung pada domain masalah.

tia

[Memperbarui]

Setelah membaca komentar dan jawaban mungkin saya harus menyatakan kembali pertanyaan saya.

Untuk program tertentu di mana semua input dibatasi, Anda dapat menentukan apakah program berhenti. Jika demikian, apa saja kendala bahasa dan apa batas input yang ditetapkan. Set maksimal dari konstruksi ini akan menentukan bahasa yang dapat disimpulkan untuk dihentikan atau tidak. Apakah ada beberapa penelitian yang telah dilakukan tentang ini?

[Perbarui 2]

inilah jawabannya, itu ya, kembali pada tahun 1967 dari http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

Bahwa masalah penghentian dapat setidaknya diselesaikan secara teoritis untuk sistem negara-terbatas telah diperdebatkan oleh Minsky pada tahun 1967 [4]: ​​“... mesin negara-terbatas, jika dibiarkan sepenuhnya untuk dirinya sendiri, pada akhirnya akan jatuh ke dalam periodik sempurna sempurna pola berulang. Durasi pola berulang ini tidak dapat melebihi jumlah kondisi internal mesin ... "

(dan jadi jika Anda tetap pada mesin turing terbatas maka Anda dapat membangun oracle)

Masalahnya bukan pada input (jelas, dengan input tidak terbatas, Anda dapat memiliki waktu berjalan tidak terbatas hanya untuk membaca input), itu pada jumlah status internal.

Ketika jumlah keadaan internal dibatasi, secara teoritis Anda dapat menyelesaikan masalah penghentian dalam semua kasus (cukup meniru sampai Anda mencapai penghentian atau pengulangan keadaan), ketika tidak, ada kasus di mana ia tidak dapat dipecahkan. . Tetapi bahkan jika jumlah negara internal dalam praktik dibatasi, juga sangat besar sehingga metode yang mengandalkan pembatasan jumlah negara internal tidak berguna untuk membuktikan penghentian program apa pun kecuali yang paling sepele.

Ada cara yang lebih praktis untuk memeriksa penghentian program. Sebagai contoh, ungkapkan mereka dalam bahasa pemrograman yang tidak memiliki rekursi atau goto dan yang struktur perulangannya semua terikat pada jumlah iterasi yang harus ditentukan pada entri loop. (Perhatikan bahwa batas tidak benar-benar terkait dengan jumlah iterasi yang efektif, cara standar untuk membuktikan penghentian loop adalah memiliki fungsi yang Anda buktikan secara ketat menurun dari satu iterasi ke iterasi lainnya dan kondisi entri Anda Pastikan positif, Anda bisa menempatkan evaluasi pertama sebagai terikat Anda).

Pertama, pertimbangkan apa yang akan terjadi jika kita memiliki detektor penghenti. Kita tahu dari argumen diagonal bahwa setidaknya ada satu program yang akan menyebabkan detektor penghentian tidak pernah berhenti atau memberikan jawaban yang salah. Tapi itu program yang aneh dan tidak mungkin.

Ada argumen lain bahwa detektor penghentian tidak mungkin, dan itu adalah argumen yang lebih intuitif bahwa detektor penghenti akan bersifat magis. Misalkan Anda ingin tahu apakah Teorema Terakhir Fermat benar atau salah. Anda cukup menulis program yang berhenti jika itu benar dan berjalan selamanya jika itu salah, dan kemudian jalankan detektor penghenti di atasnya. Anda tidak menjalankan program , Anda hanya menjalankan detektor penghenti pada program . Detektor penghenti akan memungkinkan kita untuk segera memecahkan sejumlah besar masalah terbuka dalam teori bilangan hanya dengan menulis program.

Jadi, dapatkah Anda menulis bahasa pemrograman yang dijamin akan menghasilkan program yang berhenti selalu dapat ditentukan? Yakin. Itu hanya tidak dapat memiliki loop, kondisi dan menggunakan banyak penyimpanan sewenang-wenang. Jika Anda ingin hidup tanpa loop, atau tidak ada pernyataan "jika", atau jumlah penyimpanan yang sangat terbatas, maka Anda dapat menulis bahasa yang penghentiannya selalu dapat ditentukan.

Saya merekomendasikan Anda untuk membaca Gödel, Escher, Bach . Ini adalah buku yang sangat menyenangkan dan menerangi yang, antara lain, menyentuh teorema ketidaklengkapan Gödel dan masalah berhenti.

Singkatnya untuk menjawab pertanyaan Anda: masalah penghentian dapat ditentukan selama program Anda tidak mengandung whileloop (atau salah satu dari banyak kemungkinan manifestasinya).

Untuk setiap program yang bekerja dengan jumlah memori terbatas (termasuk penyimpanan semua jenis), masalah penghentian dapat diselesaikan; yaitu program yang tidak dapat dipastikan terikat untuk mengambil semakin banyak memori dalam perjalanan.

Tetapi meskipun demikian, wawasan ini tidak berarti bahwa ia dapat digunakan untuk masalah-masalah dunia nyata, karena program penghentian, yang bekerja hanya dengan beberapa kilobyte memori, dapat dengan mudah memakan waktu lebih lama daripada waktu yang tersisa dari alam semesta untuk dihentikan.

Untuk (sebagian) menjawab pertanyaan Anda, "Apakah ada subset program yang menghindari masalah penghentian": ya, sebenarnya ada. Namun, subset ini sangat tidak berguna (perhatikan bahwa subset yang saya bicarakan adalah subset ketat dari program yang berhenti).

Studi tentang kompleksitas masalah untuk 'sebagian besar input' disebut kompleksitas kasus generik . Anda mendefinisikan beberapa subset dari input yang mungkin, membuktikan bahwa subset ini mencakup 'sebagian besar input' dan memberikan algoritma yang memecahkan masalah untuk subset ini.

Misalnya, masalah penghentian terpecahkan dalam waktu polinomial untuk sebagian besar input (pada kenyataannya, dalam waktu linier, jika saya memahami makalah dengan benar).

Namun, hasil ini agak tidak berguna karena tiga catatan samping: pertama, kita berbicara tentang mesin Turing dengan satu pita, daripada program komputer dunia nyata pada komputer dunia nyata. Sejauh yang saya tahu, tidak ada yang tahu apakah hal yang sama berlaku untuk komputer dunia nyata (meskipun komputer dunia nyata mungkin dapat menghitung fungsi yang sama seperti mesin Turing, jumlah program yang diizinkan, panjangnya dan apakah mereka berhenti mungkin benar-benar berbeda).

Kedua, Anda harus berhati-hati dengan apa yang dimaksud dengan 'input terbanyak'. Ini berarti bahwa probabilitas bahwa program acak 'panjang' n dapat diperiksa dengan algoritma ini cenderung 1 karena n cenderung tak terhingga. Dengan kata lain, jika n cukup besar, maka program acak panjang n hampir pasti dapat diperiksa oleh algoritma ini.

Program mana yang dapat diperiksa dengan pendekatan yang dijelaskan dalam makalah ini? Pada dasarnya, semua program yang berhenti sebelum mengulang suatu keadaan (di mana 'keadaan' secara kasar sesuai dengan baris kode dalam suatu program).

Meskipun hampir semua program dapat diperiksa dengan cara ini, tidak ada program yang dapat diperiksa dengan cara ini yang sangat menarik dan biasanya tidak akan dirancang oleh manusia, jadi ini tidak memiliki nilai praktis apa pun.

Ini juga menunjukkan bahwa kompleksitas kasus generik mungkin tidak akan dapat membantu kita dengan masalah penghentian, karena hampir semua program menarik (tampaknya) sulit untuk diperiksa. Atau, sebagai alternatif: hampir semua program tidak menarik, tetapi mudah diperiksa.

Ada, dan sebenarnya ada program dalam kehidupan nyata yang memecahkan masalah berhenti untuk masalah lain sepanjang waktu. Mereka adalah bagian dari sistem operasi tempat Anda menjalankan komputer Anda. Keragu-raguan adalah klaim aneh yang hanya mengatakan bahwa tidak ada program yang bekerja untuk SEMUA program lainnya.

Satu orang dengan benar menyatakan bahwa bukti penghentian tampaknya merupakan satu-satunya program yang tidak dapat dipecahkan, karena ia menelusuri sendiri seperti cermin. Orang yang sama ini juga menyatakan bahwa jika ada mesin penghenti, itu akan menjadi sihir karena akan memberi tahu kita masalah matematika yang berat dengan memberi tahu kita sebelumnya jika algoritme pemecahnya akan berhenti.

Asumsi dalam kedua kasus ini adalah bahwa mesin penghenti tidak melacak karena tidak ada bukti yang melacak. Namun, pada kenyataannya itu benar-benar melacak / menjalankan program itu dijalankan dengan input yang diberikan.

Bukti logis setidaknya sederhana. Jika tidak perlu melacak setidaknya langkah pertama, itu tidak akan membutuhkan input bersama dengan program yang sedang berjalan. Untuk dapat memanfaatkan informasi tersebut, setidaknya harus melacak langkah pertama sebelum mencoba menganalisis ke mana jalan itu menuju.

Masalah matematika yang disebutkan dalam jawaban atas adalah masalah di mana Anda tidak dapat maju cepat untuk mencari tahu jawabannya, yang berarti masalah penghentian harus terus ditelusuri hingga beberapa pola dikenali.

Jadi satu-satunya argumen praktis untuk mendapatkan dari masalah penghentian adalah bahwa mesin penghenti tidak dapat menentukan hasil dari pemecah masalah yang dioptimalkan lebih cepat daripada penyelesaian pemecah masalah.

Memberikan bukti formal untuk alasan ini lebih sulit, dan meskipun saya yakin saya bisa, mencoba menjelaskannya kepada siapa pun akademisi akan menghasilkan mereka melemparkan kera seperti temper-tantrum dan berayun dari lampu gantung. Lebih baik tidak berdebat dengan orang-orang itu.

inilah jawabannya, itu ya, kembali pada tahun 1967 dari http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

Bahwa masalah penghentian dapat setidaknya diselesaikan secara teoritis untuk sistem negara-terbatas telah diperdebatkan oleh Minsky pada tahun 1967 [4]: ​​“... mesin negara-terbatas, jika dibiarkan sepenuhnya untuk dirinya sendiri, pada akhirnya akan jatuh ke dalam periodik sempurna sempurna pola berulang. Durasi pola berulang ini tidak dapat melebihi jumlah kondisi internal mesin ... "

(dan jadi jika Anda tetap pada mesin turing terbatas maka Anda dapat membangun oracle)

Tentu saja berapa lama ini merupakan pertanyaan lain

Adakah subset program yang dapat ditentukan jika berhenti?

Iya nih.

Apakah cukup baik untuk sebagian besar program?

Tentukan "sebagian besar".

Dapatkah saya membangun satu set konstruksi bahasa yang dapat saya tentukan 'haltability' dari suatu program?

Iya nih.

Adakah hal yang hampir lengkap yang cukup bagus?

Tentukan "hampir".

Banyak orang menulis Python tanpa menggunakan whilepernyataan atau rekursi.

Banyak orang menulis Java hanya dengan menggunakan forpernyataan dengan iterator atau penghitung sederhana yang dapat dibuktikan dengan mudah; dan mereka menulis tanpa rekursi.

Sangat mudah untuk menghindari whiledan rekursi.

Untuk program tertentu di mana semua input dibatasi, dapatkah Anda menentukan apakah program berhenti?

Tidak.

Jika demikian, apa saja kendala bahasa dan apa batas input yang ditetapkan.

Um Masalah Berhenti berarti program tidak pernah dapat menentukan hal-hal tentang program serumit dirinya. Anda dapat menambahkan salah satu dari sejumlah besar kendala untuk mengatasi masalah penghentian.

Pendekatan standar untuk masalah penghentian adalah untuk memungkinkan bukti menggunakan seperangkat formalisme matematika yang sedikit "lebih kaya" daripada yang tersedia dalam bahasa pemrograman.

Lebih mudah untuk memperluas sistem bukti daripada membatasi bahasa. Pembatasan apa pun mengarah ke argumen untuk satu algoritma yang sulit untuk diungkapkan karena pembatasan tersebut.

Set maksimal dari konstruksi ini akan menentukan bahasa yang dapat disimpulkan untuk dihentikan atau tidak. Apakah ada beberapa penelitian yang telah dilakukan tentang ini?

Iya nih. Ini disebut "Teori Grup". Seperangkat nilai ditutup di bawah serangkaian operasi. Hal-hal yang cukup dipahami.