Mesin Turing + pelebaran waktu = menyelesaikan masalah penghentian?

Ada ruangwaktu relativistik (mis. Ruangwaktu MH; lihat Hogarth 1994) di mana garis dunia durasi tak terbatas dapat dimuat di masa lalu dari pengamat terbatas. Ini berarti bahwa pengamat normal dapat memiliki akses ke langkah perhitungan jumlah yang tak terbatas.

Dengan asumsi itu mungkin bagi komputer untuk berfungsi dengan sempurna untuk jangka waktu yang tak terbatas (dan saya tahu itu adalah pertanyaan besar): orang dapat membuat HM komputer yang bergerak di sepanjang garis dunia yang tak terbatas ini, menghitung masalah penghentian untuk M. tertentu. Jika M berhenti , HM mengirimkan sinyal kepada pengamat terbatas. Jika setelah jumlah langkah tak terbatas pengamat tidak mendapatkan sinyal, pengamat tahu bahwa M loop, memecahkan masalah penghentian.

Sejauh ini, ini terdengar oke bagi saya. Pertanyaan saya adalah: jika apa yang saya katakan sejauh ini benar, bagaimana ini mengubah bukti Turing bahwa masalah penghentian tidak dapat diputuskan? Mengapa buktinya gagal dalam ruang-ruang ini ?

Perhatikan bahwa bukti Turing adalah salah satu matematika, bukan fisika. Dalam model mesin Turing yang ditentukan Turing, keraguan mengenai masalah penghentian telah terbukti dan merupakan fakta matematis. Oleh karena itu, bukti Turing tidak akan 'gagal' dalam ruang-waktu, itu hanya tidak akan membuktikan apa-apa tentang hubungan masalah penghentian dan pelebaran waktu.

Namun, apa yang Anda mungkin ingin tahu adalah apakah 'mesin Turing dilasi waktu' dapat menyelesaikan masalah penghentian.

Jika Anda ingin mempelajari ini pengaruh 'pelebaran waktu' pada mesin Turing, Anda harus menentukan model formal yang dengannya kami dapat secara resmi memahami apa artinya bagi mesin Turing untuk menggunakan pelebaran waktu. Sayangnya, format ini tidak cocok untuk menyediakan model formal (kecuali orang lain telah menulis makalah tentang itu) karena membuat model terlalu luas.

Namun, bukan tidak mungkin bahwa beberapa formalisasi memang mampu menyelesaikan masalah penghentian. Makalah ini oleh Scott Aaronson, Mohammad Bavarian dan Giulio Gueltrini melihat model komputasi dengan asumsi bahwa yang disebut loop waktu-Tertutup ada dan menyimpulkan bahwa masalah penghentian memang dapat dihitung dalam model tersebut.

Mesin Turing adalah model perhitungan formal matematika, ia tidak menjawab keterbatasan fisik dan tidak peduli dengan efek relativistik. Ini berarti bahwa bukti Turing tidak gagal, karena definisi standar mesin Turing bahkan tidak mengandung gagasan "ruangwaktu".

Apa yang dapat Anda coba dan lakukan adalah mendefinisikan model komputasi yang berbeda yang diilhami oleh relativitas. Sekali lagi, ini hanya akan menjadi objek formal, dan pertanyaan apakah itu dapat atau tidak dapat menyelesaikan masalah berhenti milik bidang matematika dan tergantung pada definisi spesifik Anda. Namun, pertanyaan sebenarnya sekarang adalah apakah model baru ini memang benar menangkap efek relativistik, yaitu apakah itu benar-benar mencerminkan fisika kita dan dapat diimplementasikan di dunia kita?

Anda dapat melihat diskusi seperti itu tentang perhitungan kuantum. Kami memiliki definisi formal "mesin kuantum Turing", dan kekuatan komputasi mereka yang tepat tetap menjadi masalah terbuka dalam matematika (bahkan tidak dekat dengan masalah penghentian sekalipun). Namun, Anda dapat berargumen bahwa definisi ini tidak benar-benar mencerminkan pemahaman kita tentang fisika kuantum, dan yang lebih baik diperlukan. Ada argumen yang menunjukkan bahwa mesin seperti itu bahkan tidak dapat dibangun, sehingga kekuatan pastinya tidak berpengaruh pada tesis Church-Turing (kuat).

Kembali ke pertanyaan Anda. Ada gagasan formal tentang mesin Turing waktu yang tak terbatas , tetapi agar dapat memiliki efek pada tesis Gereja-Turing Anda memerlukannya dalam praktik. Anda mungkin tertarik pada makalah Scott , yang memiliki bagian tentang perhitungan yang memanfaatkan efek relativistik, meskipun tampaknya argumen naif tidak ada harapan (dalam arti tidak praktis, karena biaya waktu diganti dengan biaya energi).

Bukti Turing menunjukkan bahwa tidak ada mesin Turing yang dapat menyelesaikan Masalah Penghentian, tidak peduli berapa banyak waktu yang Anda berikan. Jika pesawat ruang angkasa Anda menggunakan pelebaran waktu untuk memberi komputer satu miliar tahun untuk bekerja, itu mungkin masih tidak dapat memberi tahu Anda sesuatu yang lebih pasti daripada, "Belum."

Rupanya, (Terima kasih, @ DiscreteLizard!) Jika Anda memiliki perjalanan waktu yang tidak dapat menyebabkan paradoks, Anda dapat mengatur putaran waktu yang akan menyebabkan paradoks jika komputer tidak dapat membuktikan apakah mesin Turing berhenti. Entah itu menerima jawaban dari masa depan dan mentransmisikannya kembali ke dirinya sendiri, atau berjalan selamanya (dan, secara cerdik, mengembalikan superposisi kuantum yang berubah menjadi loop waktu yang stabil). Tetapi, sebelum Anda mencoba ini, pastikan Anda aman untuk menyebabkan paradoks perjalanan waktu.

Keberatannya adalah bahwa Anda telah mendefinisikan proses yang dapat menghasilkan entropi tak terbatas di wilayah kompak dan yang tampaknya melakukannya dalam segmen terbatas dari masa lalu pengamat. Ini berarti beberapa hal

• Entropi komputasi di wilayah kompak melebihi Bekensteinterikat pada entropi (yang terikat sebanding dengan area permukaan wilayah), sehingga ia runtuh menjadi lubang hitam (langsung) dan tidak ada sinyal yang dapat menjangkau Anda dari interiornya. (Metrik Kerr menggambarkan ruangwaktu MH. Proses tak terbatas hanya diamati sampai selesai ketika pengamat masuk ke cakrawala peristiwa dalam. Mengabaikan ketidakpastian saat ini tentang fisika dari bagian tersebut, tidak ada pengamat jarak jauh yang memiliki akses ke hasil perhitungan - hanya pengamat yang telah menghilang ke dalam lubang hitam yang memiliki hasil. Ini bukan deskripsi proses komputasi yang berguna. Mengutip: "Kami memiliki oracle yang menghasilkan jawaban yang benar untuk setiap pertanyaan yang Anda tanyakan dalam waktu konstan seperti itu cara jawabannya hanya ada pada saat itu dihancurkan dengan membuangnya ke lubang hitam. ")
• Mesin Turing menghancurkan informasi setiap kali ia menimpa simbol pada pita, jadi dengan prinsip Landauer , perhitungan terbatas pada garis dunia tanpa batas yang dikompresi menjadi segmen terbatas dalam kerucut cahaya masa lalu dari pengamatan harus diamati untuk membutuhkan daya dan emisi tak terbatas. panas tak terbatas selama waktu sangat kecil diamati untuk beroperasi. Yaitu, karena penghentian dicapai dalam waktu yang terbatas, ia dicapai secara instan dari sudut pandang pengamat eksternal, sehingga semua daya dikonsumsi secara instan dan semua panas berevolusi secara instan. Atau, jika perhitungan tidak berhenti, daerah padat terus-menerus mengonsumsi daya tak terbatas dan memancarkan panas tak terbatas. Hasil bersih: lubang hitam, lagi.
• Atau, prinsip Landauer tidak berlaku untuk komputasi reversibel dan ada yang ( universal yang ) reversibel mesin Turing . Namun, mesin Turing seperti itu membutuhkan kemampuan untuk mewakili seluruh ruang keadaan komputasi potensial, yang eksponensial dalam ukuran jumlah pita yang digunakan, sehingga dengan cepat berlari ke batas Bekenstein. Kami akhirnya dapat menghindari masalah panas hanya dengan membatasi kaset dengan panjang yang dibatasi. Secara ekivalen, kita memiliki batas atas pada pita yang dapat digunakan yang dikendalikan oleh area permukaan wilayah yang memiliki garis dunia tanpa batas. Jika Anda tidak memperhitungkan ini dan perhitungan Anda menggunakan terlalu banyak pita, Anda mendapatkan lubang hitam, lagi.

Ini adalah pertanyaan terbuka yang menarik apakah dan bagaimana batasan ini berlaku untuk komputer kuantum. Mungkin saja kompleksitas komputasi yang dilakukan oleh komputer kuantum dibatasi oleh luas permukaan komputer. Jadi kita mungkin harus menggandakan luas permukaan komputer kuantum ekstrem untuk mendapatkan satu qubit komputasi yang dapat digunakan lagi. Ini dengan cepat menyebabkan komputer tidak praktis besar.

Kutipan dari Bangs, Crunches, Whimpers, dan Shrieks:

$\pi$

$(\exists x_1)(\exists x_2)\dots(\exists x_n)F(x_l,x_2,\dots,x_n)$$\gamma_1$$n$$\gamma_1$menuai dari para pekerja ini sebuah pengetahuan tentang nilai kebenaran pernyataan itu. Tetapi segera setelah bilangan bulat campuran terlibat, metode ini gagal. Namun, Hogarth (1994) telah menunjukkan bagaimana pengaturan yang lebih rumit dalam ruang relativistik umum pada prinsipnya dapat digunakan untuk memeriksa nilai kebenaran dari setiap pernyataan aritmatika dari kompleksitas kuantitatif acak. Dalam ruangwaktu seperti itu sulit untuk melihat bagaimana mempertahankan sikap bahwa kita tidak memiliki gagasan yang jelas tentang kebenaran dalam aritmatika.