Mungkinkah Masalah Pemutusan "diselesaikan" dengan melarikan diri ke deskripsi komputasi tingkat tinggi?

21

Saya baru-baru ini mendengar analogi yang menarik yang menyatakan bahwa bukti Turing tentang ketidakpastian masalah penghentian sangat mirip dengan paradoks tukang cukur Russell.

Jadi saya bertanya-tanya: matematikawan akhirnya berhasil membuat teori himpunan konsisten dengan beralih dari formulasi naif Cantor di lapangan ke sistem aksioma yang lebih kompleks (teori himpunan ZFC), membuat pengecualian penting (batasan) dan penambahan di sepanjang jalan.

Jadi apakah mungkin untuk mencoba dan menghasilkan deskripsi abstrak dari perhitungan umum yang lebih kuat dan lebih ekspresif daripada mesin Turing, dan yang dengannya seseorang dapat memperoleh bukti eksistensial atau bahkan mungkin sebuah algoritma untuk memecahkan masalah penghentian untuk mesin Turing yang sewenang-wenang?

computability turing-machines computation-models halting-problem H2CO3
sumber
1
Selamat datang di Pertukaran Stack Ilmu Komputer. Silakan baca cs.stackexchange.com/tour.jika Anda belum melakukannya. --- Apa yang Anda coba untuk model yang lebih kuat dari TM? Apa yang menghalangi Anda?
babou
2
@ Babou Sebaliknya, Anda membutuhkan model yang kurang kuat.
Yuval Filmus
2
@YuvalFilmus Nah, OP meminta model yang lebih kuat, bukan yang lebih lemah. --- dengan permintaan maaf kepada H2CO3 ... Pertanyaan saya sebenarnya adalah lelucon karena ini adalah pertanyaan standar ketika orang-orang mengirimkan pekerjaan rumah mereka sebagai pertanyaan. Itu tentu saja tidak sesuai di sini, karena tidak ada yang mengharapkan Anda akan menemukan model seperti itu. Saya harap Anda tidak akan terlalu asam.
babou
1
Anda mungkin ingin membaca tentang Hypercomputation en.wikipedia.org/wiki/Hypercomputation .
Eric Towers

Jawaban:

15

Anda tidak dapat benar-benar membandingkan. Teori himpunan naif memiliki paradoks yang dihilangkan oleh teori himpunan ZFC. Teorinya harus ditingkatkan untuk konsistensi, karena asumsi dasar karya ilmiah adalah bahwa konsistensi dapat dicapai (kalau tidak penalaran menjadi bisnis untung-untungan). Saya kira ahli matematika berharap itu harus mungkin, dan bekerja untuk menyelesaikan masalah.

Tidak ada situasi seperti itu dengan teori komputasi dan masalah penghentian. Tidak ada paradoks, tidak ada ketidakkonsistenan. Kebetulan bahwa tidak ada mesin Turing yang dapat memecahkan masalah penghentian TM. Ini hanya sebuah teorema, bukan sebuah paradoks.

Jadi mungkin beberapa terobosan dalam pemahaman kita tentang alam semesta akan mengarah pada model perhitungan di luar apa yang dapat kita bayangkan sekarang. Satu-satunya peristiwa semacam itu, dalam bentuk yang sangat lemah, yang masih ada di dalam dunia TM, kemungkinan adalah komputasi kuantum. Selain dari contoh yang sangat lemah ini yang menyentuh kompleksitas (berapa lama waktu yang dibutuhkan?) Daripada kemampuan komputasi (apakah layak?), Saya ragu ada orang di planet ini yang memiliki petunjuk bahwa kemampuan komputasi di luar TM diharapkan.

Selain itu, masalah penghentian adalah konsekuensi langsung dari kenyataan bahwa mesin Turing dijelaskan oleh sepotong teks yang terbatas, urutan simbol. Ini sebenarnya benar dari semua pengetahuan kita (sejauh yang kita tahu), dan itulah sebabnya pidato dan buku sangat penting. Ini berlaku untuk semua teknik kami untuk menggambarkan bukti dan perhitungan.

Jadi, bahkan jika kita menemukan cara untuk memperluas cara kita menghitung, katakanlah dengan mesin T +. Entah itu berarti bahwa kami telah menemukan cara untuk mengekspresikan pengetahuan di luar menulis dokumen yang terbatas, dalam hal ini semuanya jatuh dari yurisdiksi saya (saya mengklaim ketidakmampuan mutlak) dan mungkin milik orang lain. Atau masih dapat diekspresikan dalam dokumen yang terbatas, dalam hal ini akan memiliki masalah tersendiri untuk mesin T +. Dan Anda akan mengajukan pertanyaan lagi.

Sebenarnya situasi itu memang ada secara terbalik. Beberapa jenis mesin lebih lemah dari mesin Turing, seperti Linear Bounded Automata (LBA). Mereka cukup kuat, tetapi dapat ditunjukkan persis seperti yang dilakukan untuk TM bahwa LBA tidak dapat memecahkan masalah penghentian untuk LBA. Tetapi TM dapat menyelesaikannya untuk LBA.

Akhirnya, Anda dapat membayangkan model komputasi yang lebih kuat dengan memperkenalkan oracle, yaitu perangkat yang dapat memberikan jawaban untuk masalah tertentu, dan dapat dipanggil oleh TM untuk mendapatkan jawaban, tetapi sayangnya tidak ada secara fisik. TM oracle-extended seperti itu adalah contoh dari mesin T + yang saya pertimbangkan di atas. Beberapa dari mereka dapat memecahkan masalah penghentian TM (secara abstrak, bukan untuk yang sebenarnya), tetapi tidak dapat memecahkan masalah Berhenti sendiri, bahkan secara abstrak.

babou
sumber
Dengan asumsi ZFC konsisten, itu masih belum lengkap yaitu ada kalimat bahwa kita tidak dapat membuktikan atau membantah dari ZFC, dan ini terkait erat dengan penghentian masalah yang tidak dapat diselesaikan, jika penghentian dapat dipecahkan kita dapat membuktikan atau menyangkal semua kalimat. Ini matematika, dan ini bukan ketidakkonsistenan yang harus dipecahkan tetapi juga sebuah teorema (Gödel)
Hernan_eche
@Hernan_eche Yah ... ya dan ... apa ...? Jika Anda berpikir bahwa inkonsistensi tidak lebih buruk daripada ketidaklengkapan, itu adalah penilaian pribadi Anda. Saya ragu sebagian besar ahli matematika akan setuju. Anda mungkin tidak menyukai TM yang tidak berakhir. Tapi apakah Anda ingin mereka lebih baik mengakhiri selalu, mengatakan kadang-kadang ya dan kadang tidak, pada input yang sama. Apa yang akan Anda dapatkan dari jawabannya? Dan jika Anda berpikir non-determinisme ... pikirkan dua kali.
babou
Saya berkomentar hanya untuk menjelaskan bahwa Ilmu Komputer dan Matematika melawan masalah yang sama, untuk menghindari pembaca salah menafsirkan jawaban seolah-olah matematika diselesaikan dengan fondasi masalah dengan ZFC dan menghentikan masalah hanyalah masalah ilmu komputer, bukan itu masalahnya, ada korespondensi satu ke satu antara ketidaklengkapan dan menghentikan masalah, itu masalah yang sama. Saya tidak berpikir ketidaklengkapan menjadi lebih buruk atau lebih baik daripada ketidakkonsistenan, tetapi saya pikir ketidaklengkapan akan menjadi ketidakkonsistenan jika Anda ingin membangun sistem urutan yang lebih tinggi.
Hernan_eche
17

Nah, Anda selalu dapat mempertimbangkan mesin Turing yang dilengkapi dengan oracle untuk masalah menghentikan mesin Turing biasa. Artinya, mesin baru Anda memiliki pita khusus, di mana ia dapat menulis deskripsi mesin Turing biasa dan inputnya dan bertanya apakah mesin itu berhenti pada input itu. Dalam satu langkah, Anda mendapatkan jawaban, dan Anda dapat menggunakannya untuk melakukan perhitungan lebih lanjut. (Tidak masalah apakah itu dalam satu langkah atau tidak: itu akan cukup jika dijamin dalam beberapa langkah terbatas.)

Namun, ada dua masalah dengan pendekatan ini.

  1. Mesin Turing yang dilengkapi dengan oracle semacam itu tidak dapat memutuskan masalah penghentian mereka sendiri: Bukti Turing tentang ketidakpastian masalah penghentian biasa dapat dengan mudah dimodifikasi ke pengaturan baru ini. Bahkan, ada hierarki yang tak terbatas, yang dikenal sebagai "Gelar Turing", yang dihasilkan dengan memberikan tingkat hierarki berikutnya sebuah ramalan untuk menghentikan masalah yang sebelumnya.

  2. Tidak ada yang pernah menyarankan cara apa pun di mana oracle semacam itu dapat diimplementasikan secara fisik. Semuanya sangat baik sebagai perangkat teoretis tetapi tidak ada yang tahu cara membangunnya.

Juga, perhatikan bahwa ZFC, dalam arti tertentu, lebih lemah dari teori himpunan naif, tidak lebih kuat. ZFC tidak bisa mengekspresikan paradoks Russell, sedangkan teori himpunan naif bisa. Dengan demikian, analogi yang lebih baik adalah dengan menanyakan apakah masalah penghentian dianggap layak untuk model komputasi yang lebih lemah daripada mesin Turing. Misalnya, masalah penghentian untuk deterministic finite automata (DFAs) dapat ditentukan, karena DFA dijamin akan berhenti untuk setiap input.

David Richerby
sumber
Saya pikir masalah penghentian sendiri dapat dipecahkan oleh keluarga automata jika itu sepele, yaitu apakah mereka semua berhenti atau tidak ada yang melakukannya (yang mungkin dianggap aneh dalam kasus ini).
babou
1
@ Babou: bagaimana dengan automata di mana mesin 0 loop selamanya, mesin 1 menghasilkan FALSE jika inputnya 0 maka output BENAR dan kemudian berhenti. Semua mesin lain menghasilkan SALAH dan kemudian berhenti. Apakah itu keluarga automata di mana program 1 memecahkan masalah penghentian yang tidak sepele? Atau apakah ini bahkan bukan sebuah keluarga robot, karena kekurangan beberapa properti, misalnya komposisi apa pun?
Steve Jessop
@SteveJessop Ya, Anda (dan Davis Richerby) mungkin benar. Yang menggangguku adalah bahwa ini adalah contoh yang dibuat-buat. Anda membangun keluarga yang sangat lemah sehingga salah satu mesin dalam keluarga tersebut menjadi penentu untuk seluruh keluarga. Tetapi, ketika Anda mencurigai diri Anda (lihat komentar Anda tentang komposisi), mungkin ada beberapa properti penutupan dasar yang hilang sehingga masalahnya dapat disepelekan. Saya tidak memiliki jawaban yang siap, dan saya setuju bahwa komentar saya memerlukan lebih banyak kualifikasi untuk apa yang merupakan keluarga automata, tetapi contoh balasan Anda membuat saya tidak yakin.
babou
3

Peringatan: Jawaban filosofis / tidak keras

Ini mungkin sedikit "filosofis", tapi saya pikir itu cocok dengan semangat pertanyaan Anda.

Mesin yang tidak dapat diulang

Batu sudut bukti dari masalah penghentian adalah bahwa mesin Turing berperilaku seperti fungsi: Untuk input yang sama selalu memberikan hasil yang sama. Jika Anda menghapus properti ini, Anda tidak harus berurusan dengan masalah penghentian "umum", dalam arti bahwa mesin dapat menemukan propertinya sendiri. Tetapi Anda juga kehilangan banyak sifat teoritis yang diinginkan dari mesin seperti itu.

Menghapus properti

Ini sedikit seperti beralih dari teori himpunan ke teori kategori: Anda kehilangan beberapa "paradoks" dengan kehilangan batasan. Tetapi hasilnya jauh lebih sulit untuk ditangani.

Dalam hal ini berarti: Anda tidak akan tahu jika mesin menyajikan Anda hasil yang "benar". Segera setelah Anda selalu dapat memutuskan hasil mana yang benar, Anda harus berurusan dengan semacam "masalah terputus-putus" dengan menerapkan mesin itu sendiri dan membuat kontradiksi. Jadi mesin seperti itu mungkin tidak akan terlalu berguna.

stefan.schwetschke
sumber
1
Terima kasih, hal "mesin yang tidak dapat diulang" itu terdengar cukup menarik, sebenarnya. Saya tidak merasa diri saya cukup kompeten untuk dengan nyaman mengatakan beberapa kebijaksanaan tentang program pemeriksaan diri yang cerdas (karena naluri saya adalah bahwa mereka masih dapat diekspresikan sebagai mesin Turing), tetapi saya merasa mereka mungkin sangat berguna untuk beberapa masalah.
H2CO3
1
Bagaimana memberi contoh non repeatability? Bagaimana Anda mendefinisikan penghentian dalam kasus itu. Kesulitan utama adalah bahwa, ketika Anda mencoba mendefinisikan model perhitungan yang aneh, biasanya yang gedanken, Anda harus mendefinisikan arti penghentian, dan input apa yang harus dianalisis oleh mesin penentu, dan mungkin beberapa hal lain yang tidak sepele. Lihat misalnya kasus non-determinisme . Belum lagi masalah apa yang dapat dianggap sebagai model komputasi (mungkin bukan koleksi mesin ad hoc).
babou
1
@ H2CO3 Mesin yang tidak dapat diulang hanyalah sejenis "percobaan Gedanken" tentang properti apa yang harus Anda korbankan untuk keluar dari "masalah penghentian umum" (membangun kontradiksi dengan membiarkan mesin memeriksa sendiri). Anda akan mendapatkan mesin yang terkadang benar, tetapi Anda tidak tahu kapan. Ini seperti program yang menghitung angka lotre untuk minggu depan. Saya dapat dengan mudah memberikan Anda program semacam itu. Bagian yang sulit bagi Anda untuk memutuskan, mana dari sekian banyak program yang akan saya berikan kepada Anda adalah yang benar ...
stefan.schwetschke
2

Masalah Pemutusan tidak diformulasikan untuk mengekspresikan batasan dari Mesin Turing, tetapi untuk mengekspresikan batasan dari semua sistem logika yang dapat diekspresikan menggunakan jumlah simbol yang terbatas. Setelah sistem logika memiliki kemampuan untuk mengekspresikan solusi untuk masalah kompleksitas tertentu, ia juga akan memiliki kemampuan untuk mengekspresikan masalah yang tidak dapat dipecahkan. Setiap perluasan sistem logika yang cukup untuk mengekspresikan solusi untuk semua masalah yang tidak dapat dipecahkan sebelumnya juga akan mencakup kemampuan untuk mengekspresikan masalah baru yang tidak dapat diselesaikan.

Dengan spesifikasi "Mesin Turing yang Ditingkatkan" tertentu, dimungkinkan untuk menentukan "Mesin Turing Super-Enhanced" yang dapat memeriksa program untuk ETM dan melaporkan apakah akan berhenti, tetapi SETM hanya akan dapat menganalisis program untuk ETM - tidak akan bisa menganalisis program SETM. Tidak ada cara untuk mendefinisikan mesin yang dapat menganalisis program untuk dirinya sendiri dan menentukan apakah mereka berhenti karena tindakan menambahkan fitur baru akan menciptakan persyaratan baru untuk penganalisa sendiri, dan tidak ada cara untuk membuat fitur "mengejar" persyaratan. .

supercat
sumber
1

Mesin seperti itu telah dibayangkan, dan disebut mesin super-Turing . Beberapa kelas utama mesin super-turing adalah

  • Mesin bilangan real (yaitu komputer analog)
  • Mesin Turing diberi waktu tak terbatas
  • Mesin turing non-deterministik

Tidak semua mesin super-turing dapat memecahkan masalah penghentian (mesin turing Nondeterminnistic, khususnya, tidak bisa). Namun, mesin konseptual telah dibuat, setidaknya dalam eksperimen pemikiran.

Cort Ammon - Pulihkan Monica
sumber