Bagaimana model hypercomputation mengatasi Masalah Halting?

Komputasi berlebihan mengacu pada model komputasi yang tidak mungkin untuk disimulasikan menggunakan mesin Turing. (Hypercomputer belum tentu dapat direalisasikan secara fisik!) Beberapa hypercomputer memiliki akses ke sumber daya yang memungkinkan Masalah Pemutusan untuk mesin Turing standar dapat diselesaikan. Sebut ini "kekuatan super": komputer super dengan kekuatan super dapat memutuskan apakah mesin Turing standar berakhir.

"Kekuatan super" macam apa yang digunakan oleh hypercomputer?

Tesis Ed Blakey menetapkan kerangka formal untuk mengklasifikasikan beberapa jenis sumber daya utama yang digunakan dalam hypercomputing, tetapi tidak mencoba untuk memberikan survei komprehensif negara adidaya. Saya tidak tertarik pada daftar hypercomputer (ada daftar yang bagus di artikel Wikipedia), tetapi dalam memahami apa yang "saus khusus" gunakan masing-masing model, mungkin dianggap sebagai jenis sumber daya yang unik.

Pertanyaan ini diilhami oleh Seberapa mendasar hal itu tidak dapat dipastikan? . Juga terkait adalah Apa artinya untuk membantah tesis Gereja-Turing? yang menghasilkan banyak diskusi menarik, dan Apakah ada model perhitungan yang saat ini sedang dipelajari dengan kemungkinan lebih kuat daripada Mesin Turing? .

Di kertas Pada kekuatan multiplikasi di mesin akses acak telah dibuktikan oleh Hartmanis bahwa, jika kita menambahkan instruksi perkalian biaya satuan dalam RAM (disebut MRAM) maka untuk model ini P = NP. Selain itu bahasa-bahasa yang diputuskan dalam waktu polinomial dalam model MRAM adalah bahasa-bahasa di PSPACE.

Sebagaimana dinyatakan dalam makalah, hasil ini menunjukkan bahwa perkalian memiliki kompleksitas yang sama dengan penambahan iff P = PSPACE.

Hasil yang lebih terkait yang saya dengar, adalah bahwa jika kita menambahkan instruksi pembagian dengan ketepatan tak terbatas dalam RAM maka kita dapat memecahkan masalah yang tidak dapat ditentukan. Namun saya tidak dapat menemukan kertas yang membuktikan hasil ini. Jika ada yang akrab dengan itu, silakan komentar dan saya akan memperbarui jawabannya.

Jadi, Anda telah menemukan bahwa TM tidak dapat menyelesaikan setiap masalah! Langkah pertama yang diambil Turing dan sangat logis (meskipun tidak sepele jika Anda menganggap keadaan komputasi pada waktu itu) adalah ramalan.

Secara informal, Anda menambahkan modul kotak-hitam baru ke mesin Anda yang dapat "entah bagaimana" menyelesaikan masalah yang tidak dapat dilakukan mesin Anda, katakanlah masalah penghentian. Tentu saja, nubuat hanyalah abstraksi matematis dan tidak ada rahasia di balik kerja batin mereka. Secara pribadi, saya tidak melihat cara apapun bahwa oracle dapat digunakan untuk menemukan model yang menyanggah tesis Church-Turing.

• Memanipulasi waktu dan ruang

Karena masalah dengan memecahkan masalah penghentian adalah mengetahui kapan mesin akan berhenti, dengan menjalankan mesin dalam ruangwaktu yang berbeda dari waktu kita dapat memungkinkan Anda untuk menyelesaikannya. Dari sumber saya ketika saya sedang menulis laporan tentang model yang dapat diselesaikan secara efisien$NP$, fisikawan teoritis percaya bahwa kondisi itu terpenuhi di dekat tepi lubang hitam. Untuk melakukan ini, Anda harus memiliki mesin komputasi yang sangat dekat dengan lubang hitam tetapi tidak ke cakrawala acara (sehingga tidak tertarik). Kemudian Anda menyelam di lubang hitam dan Anda dapat meninjau seluruh waktu tak terbatas mesin Anda dalam waktu yang terbatas. Ini mungkin berarti Anda ditarik ke dalam lubang hitam, jadi saya kira itu tidak akan diimplementasikan dan diuji bahkan jika kita bisa mencapai lubang hitam. Ini semua bersifat informal, Anda mulai membaca pendekatan fisika yang lebih teoretis dari artikel wikipedia di Malament-Hogarth_spacetime . Kutipan yang bermanfaat juga merupakan artikel Apakah relativitas umum memungkinkan pengamat untuk melihat keabadian dalam waktu yang terbatas?

• Mesin Zeno dapat menyelesaikan masalah apa pun dalam 2 detik, tetapi ini adalah konstruksi hipotetis matematis, di mana setiap langkah membutuhkan separuh waktu sebelum itu dan waktu pertama membutuhkan 1 detik. Itu tidak memberikan solusi dunia nyata yang bisa Anda terapkan.

Ada model-model lain yang saya tahu, tetapi saya pikir mereka hanya memperluas ide-ide yang saya sajikan di sini atau merupakan konstruksi matematika murni, sehingga mereka lebih seperti "trik rapi" daripada sesuatu yang dapat menyanggah tesis Church-Turing.

Tidak persis seperti yang Anda tanyakan, tetapi Scott Aaronson memiliki sebuah makalah, dijelaskan dengan baik di sini tentang mesin Turing dengan kemampuan untuk melakukan perjalanan waktu, tetapi dengan persyaratan konsistensi diri (yaitu Anda tidak dapat kembali untuk mengubah masa lalu. Anda dapat mengamati masa depan , tetapi harus konsisten dengan saat ini).