Apakah tidak dapat dipecahkannya Masalah N-Tubuh setara dengan Masalah Berhenti

16

Tidak ada solusi analitik umum untuk masalah n-body yang dapat menghasilkan fungsi analitik yang dapat digunakan untuk memberikan status sistem n-body pada waktu acak t dengan presisi yang tepat. Namun, ada beberapa kasus khusus dari sistem n-body yang fungsi analitiknya diketahui.

Dalam banyak cara yang sama, tidak ada algoritma umum yang dapat memprediksi hasil dari mesin Turing yang sewenang-wenang. Meskipun, ada banyak jenis mesin Menghidupkan yang dapat ditentukan untuk berhenti atau berjalan selamanya.

Apakah kedua hasil ini setara? Apakah bukti salah satu dari ini menyiratkan yang lain? Apakah mesin ajaib yang mampu memecahkan masalah penghentian dapat memprediksi keadaan sistem n-tubuh dengan presisi yang tepat? Atau sebaliknya, apakah solusi analitik umum untuk masalah n-body memungkinkan kita untuk memutuskan masalah penghentian pada mesin Turing yang sewenang-wenang?

Dugaan awal saya tentang cara mendekati ini adalah untuk menunjukkan bahwa sistem n-body di bawah gravitasi sudah lengkap. Saya curiga bahwa itu mempertimbangkan alam semesta adalah Turing lengkap dan pada dasarnya beroperasi di bawah gravitasi (dan beberapa kekuatan lain yang berperilaku sama), tetapi saya tidak tahu bagaimana cara membuktikannya.

Tapi saya skeptis bahwa pendekatan itu cukup mengingat saya menemukan itu mungkin (meskipun saya pikir tidak mungkin) bahwa kurangnya solusi umum analitik untuk masalah n-tubuh bisa independen dari itu menjadi Turing lengkap.

Sunting: Setelah membaca beberapa pertanyaan terkait tangensial lainnya, saya menyadari bahwa jumlah dimensi tempat gravitasi beroperasi dapat relevan dengan pertanyaan tersebut. Saya secara khusus bertanya tentang gravitasi dalam 3 dimensi spasial. Tapi, mengingat fakta seperti Anda membutuhkan setidaknya 3 aturan untuk membuat mesin Turing universal dan gravitasi dalam 2 dimensi hanya akan memiliki hukum terbalik bukannya hukum kuadrat terbalik ∝ 1 / r 2 yang menghasilkan orbit tanpa tertutup , Saya dapat melihat bahwa gravitasi dalam tiga dimensi adalah Turing Lengkap, tetapi tidak dalam dua atau satu.∝1/r∝1/r2

computability turing-machines undecidability computation-models Shufflepants
sumber
1
Adalah pilihan Anda untuk mengajukan pertanyaan yang Anda inginkan, tetapi saya khawatir Anda mungkin menggunakan kata-kata dan konsep teknis tanpa peduli apakah mereka dapat memiliki makna dalam konteks di mana Anda memilih untuk menggunakannya. Itu tidak terlalu ilmiah. Saya tidak mengatakan itu salah untuk berspekulasi, tetapi menyerukan hati-hati. Apa yang bisa berarti untuk masalah n-tubuh menjadi Turing lengkap? Apa yang mungkin merupakan pencacahan Gödel untuk masalah n-tubuh? Ngomong-ngomong, Turing selalu mengeja dengan huruf T besar, kami berutang setidaknya kepadanya sebanyak itu.
babou
Maksud saya masalah n-tubuh menjadi Turing lengkap dalam arti yang sama bahwa Game of Conway's Life adalah Turing lengkap; Anda dapat mengatur sistem partikel titik gravitasi dan menggunakan evolusi kondisi sistem itu untuk melakukan perhitungan.
Shufflepants
Saya tidak tahu apa yang bisa dikodekan dalam posisi, kecepatan, atau percepatan sejumlah partikel titik dari massa yang berbeda atau identik. Saya secara eksplisit bertanya apakah ada pengkodean seperti itu karena saya tidak tahu.
Shufflepants
1
Permainan kehidupan Conway adalah sejenis teori otomat seluler, struktur yang sangat berbeda, seperti mesin turing. Jadi kita dapat membayangkan bahwa penyandian yang satu ke yang lain dapat dilakukan. Tapi masalah n-body adalah di dunia persamaan diferensial, fungsi kontinu dan semacamnya ... Saya agak ragu tentang pengkodean satu ke yang lain. Apa yang mungkin Anda harapkan (walaupun saya ragu, dan saya juga tidak kompeten) adalah bahwa tidak adanya solusi analitik untuk masalah n-tubuh akan menjadi konsekuensi dari kontradiksi internal pada teori apa pun yang dapat mengungkapkan masalah itu, sedikit mirip dengan bukti masalah tersendat-sendat.
babou
1
Sebenarnya kesempatan terbaik Anda adalah sebagai masalah matematika. Fisikawan akan memberi tahu Anda bahwa n-tubuh kacau, sensitif terhadap kupu-kupu, sehingga fluktuasi kuantum akan membunuh semua pengkodean jarak jauh, atau prediksi evolusi sistem, yang tidak terlalu baik untuk Mesin Turing. Orang-orang matematika mungkin mengatakan sesuatu yang lebih buruk, tapi untungnya saya tidak tahu apa itu.
babou

Jawaban: