Apakah ada hubungan antara masalah penghentian dan entropi termodinamika?

Alan Turing mengusulkan model untuk mesin (Turing Machine, TM) yang menghitung (angka, fungsi, dll.) Dan membuktikan Teorema Henti .

TM adalah konsep abstrak dari mesin (atau mesin jika Anda suka). Teorema Penghentian adalah hasil ketidakmungkinan. Mesin Carnot (CE) adalah konsep abstrak dari mesin panas dan Carnot membuktikan Teorema Carnot , hasil ketidakmungkinan lain yang terkait dengan entropi termodinamika.

Mengingat bahwa TM secara fisik dapat direalisasikan (setidaknya sebanyak CE, atau mungkin tidak?) Adakah pemetaan atau representasi atau "isomorfisme" dari TM atau CE yang dapat memungkinkan untuk menyatukan hasil ini dan di samping terhubung ke entropi?

Tentu saja ada formulasi TM dan Teorema Halting dalam hal teori informasi algoritmik (misalnya Chaitin, Kolmogorov, dll.) Dan entropi (dalam konteks itu). Pertanyaannya menanyakan konsep entropi yang lebih fisik (jika dalam proses jawaban potensial, entropi algoritme muncul, itu baik-baik saja, tetapi bukan pertanyaan persisnya yang ditanyakan).

Seseorang juga dapat memeriksa pertanyaan lain dalam fisika. See yang menghubungkan ketidakpastian kuantum dengan hukum ke-2 termodinamika. Lihat juga: karakterisasi entropi aljabar , karakterisasi algoritme entropi , ulasan dan koneksi antara berbagai formulasi entropi

Saya sama sekali tidak ahli dalam bidang ini, tetapi saya yakin Anda akan tertarik pada komputasi reversibel . Ini melibatkan, antara lain, studi tentang hubungan antara proses yang secara fisik dapat dibalik dan proses yang secara logis dapat dibalik. Saya pikir akan adil untuk mengatakan bahwa "pendiri" bidang itu adalah / adalah Ralph Landauer dan Charles H Bennett (keduanya dari riset IBM, saya pikir.)

Ini menyentuh komputasi kuantum dan teori informasi kuantum, tetapi juga memeriksa pertanyaan seperti "apa batas perhitungan dalam hal waktu, ruang dan energi?" Diketahui, (jika saya ingat dengan benar) bahwa Anda dapat membuat energi yang dibutuhkan untuk melakukan perhitungan yang dapat dibalik secara sewenang-wenang dengan membuatnya memakan waktu lama secara sewenang-wenang. Artinya, energi waktu (= tindakan ) yang diperlukan untuk melakukan perhitungan yang dapat dibalik dapat dibuat konstan. Ini bukan kasus untuk perhitungan non-reversibel.$\times$

Banyak orang yang belajar di bidang ini juga bekerja pada komputasi kuantum dan fisika awal (gagasan bahwa alam semesta adalah automata seluler kuantum besar). Nama-nama peneliti yang muncul di benak adalah Ed Fredkin , Tommaso Toffoli dan Norm Margolus .

Pertanyaan-pertanyaan ini benar - benar tentang topik untuk ilmu komputer. Bukan hanya untuk teori (yang meliputi matematika keren dan juga fisika keren) tetapi untuk insinyur yang ingin mengetahui batas akhir perhitungan. Apakah ada volume minimum atau energi yang diperlukan untuk menyimpan sedikit informasi? The tindakan yang dibutuhkan untuk melakukan perhitungan reversibel mungkin konstan, tetapi ada batas pada apa yang konstan? Ini adalah pengetahuan kritis bagi para insinyur yang berusaha mendorong batas-batas apa yang mungkin.

Saya tidak familier dengan Teorema Carnot, kecuali apa yang baru saja saya baca di Wikipedia, tetapi bahkan dari pengantar sepintas itu, ada hubungan dalam struktur buktinya, dan itu mungkin menarik bagi Anda, karena itu adalah teknik pembuktian yang berlaku di banyak domain.

Keduanya adalah bukti berdasarkan kontradiksi yang menunjukkan bahwa tidak ada sesuatu di kelas tertentu yang memiliki properti, Anda mengira bahwa beberapa instance benar-benar memiliki properti itu, dan kemudian menunjukkan bahwa kontradiksi mengikuti.

Masalah Pemutusan menarik karena kontradiksi muncul dari beberapa interaksi diri mengenai contoh tertentu (yang merupakan mesin M yang dapat menentukan apakah mesin sewenang-wenang akan berhenti dengan input yang diberikan). Secara khusus, Anda membangun mesin baru yang menyertakan M sebagai komponen, dan kemudian memberi makan mesin baru ke M.

Seseorang dengan pengetahuan lebih banyak tentang Teorema Carnot dapat menguraikannya (yang saya tidak memenuhi syarat untuk melakukannya), tetapi tampaknya kontradiksi muncul dari jenis mesin panas yang dapat Anda bangun jika Anda memiliki instance dengan properti yang ada.

Jadi kedua kasus melibatkan pembangunan:

• Misalkan beberapa X memiliki properti P.
  • Dari X, build terkait Y.
  • Hubungan antara X dan Y saling bertentangan.
• Oleh karena itu, tidak ada X yang memiliki properti P.

Namun, tampaknya ada perbedaan, dalam hal kontradiksi dalam teorema Halting adalah kontradiksi logis murni, dan akan kontradiktif dalam setiap pengaturan logika klasik. Teorema Carnot, seperti yang saya mengerti, hanya bertentangan dengan hukum kedua termodinamika. Dari perspektif logis, itu aksioma, jadi jika Anda mengambil aksioma yang berbeda di mana hukum termodinamika kedua tidak berlaku, Teorema Carnot tidak akan menjadi teorema, karena kontradiksi tidak akan ada. (Seperti apa bentuk formalisasi termodinamika tanpa hukum kedua adalah jenis pertanyaan yang mengarahkan geometer ke geometri non-Euclidean.)

Saya seorang ahli fisika tetapi saya tidak melihat adanya koneksi. Mesin Turing adalah objek matematika murni dan ketidakpastian masalah berhenti tidak tergantung pada realisasi fisik apa pun.

pertanyaan beragam-topik beragam unf ini tidak memiliki jawaban / sentuhan sederhana / mudah pada bidang-bidang aktif penelitian TCS. namun itu adalah pertanyaan langka yang menanyakan tentang hubungan antara fisika & TCS yang telah menarik minat saya selama ini. ada beberapa arah berbeda untuk melanjutkan ini. jawaban dasarnya adalah "pertanyaan terbuka" tetapi dengan beberapa penelitian aktif / modern menyentuhnya dan mengisyaratkan koneksi.

• ada beberapa masalah mengejutkan / mendalam yang belum diputuskan dari fisika maju. misalnya dari sistem dinamik. Namun, belum melihat ini terhubung ke entropi per se, tetapi entropi dikaitkan dengan semua sistem fisik (misalnya orang dapat melihat ini dalam teori kimia), jadi setidaknya harus ada hubungan tidak langsung.

• entropi memang muncul di CS tetapi lebih dalam bentuk teori informasi dan teori pengkodean. kelahiran teori pengkodean melibatkan definisi / analisis entropi yang terkait dengan kode komunikasi oleh Shannon. coba teori online Entropy & Informasi ref yang bagus ini oleh Gray

• entropi juga dikaitkan kadang-kadang dikaitkan dengan mengukur keacakan dalam PRNG. ada koneksi pemisahan kelas kompleksitas (misalnya P =? NP) ke PRNGs dalam makalah "Bukti Alami" yang terkenal oleh Razborov / Rudich. ada penelitian berkelanjutan tentang subjek ini.

• Anda menyebutkan termodinamika dan hubungannya dengan TCS. ada hubungan yang mendalam antara magnetisasi dalam gelas spin dalam fisika dan masalah lengkap NP yang dipelajari pada titik transisi SAT. di sana (lagi) sistem fisik memiliki entropi yang terkait dengannya tetapi mungkin telah dipelajari lebih banyak dalam konteks fisika daripada konteks TCS.

Ada masalah pemikiran sederhana yang kadang-kadang digunakan sebagai pengantar paradigma komputasi non-konvensional:

Anda memiliki dua bola lampu dan sakelar on-off masing-masing. Seseorang membuka dan menutup kedua lampu satu demi satu. Bagaimana Anda menentukan yang mana yang ditutup terlebih dahulu dan mana yang ditutup terakhir? Tentukan jumlah minimum yang Anda perlukan untuk membuka lampu untuk memutuskan masalah ini.

Sebagian besar ilmuwan komputer biasanya mencoba menemukan beberapa solusi berbasis logika boolean. Jawabannya adalah (setidaknya salah satunya): dengan menyentuh bola lampu dan melihat mana yang lebih panas.

Paradigma berbasis panas ada dalam ilmu komputer: simulated annealing adalah algoritma yang dikenal (komputer kuantum D-gelombang adalah mitra kuantum dari algoritma).

Sekarang apakah ada hubungannya dengan masalah Hentikan?

Karya klasik Chaitin dan Calude tentang masalah Halting melalui konsep bilangan Omega dapat dihubungkan dengan formulasi probabilistik dari masalah Halting. Ini adalah risalah yang lebih baru tentang masalah yang dapat saya pikirkan ... dan tidak ada hubungan yang jelas dengan entropi (termodinamika). Sekarang jika entropi informasi (dalam arti Shannon) baik untuk Anda, angka Omega mengkodekan dengan cara yang paling ringkas masalah Menghentikan, dalam arti terikat Shannon.

Singkatnya, angka Omega adalah probabilitas bahwa program acak berhenti. Mengetahui konstanta akan memungkinkan enumerasi semua pernyataan matematika yang valid (kebenaran, aksioma, dll) dan tidak dapat dihitung. Calude menghitung versi Omega dengan mengubah ukuran probabilitas seragam dengan ukuran berbanding terbalik dengan panjang program acak dan dengan menggunakan pengkodean bebas awalan. Jadi kita bisa berbicara tentang Omega Chaitin dan Omega Calude.

Ya !, anehnya saya sudah memikirkan hal ini .. Inilah idenya:

Langkah pertama

Model the Maxwell's Demon sebagai program komputer. Lalu, Bagaimana Iblis mengetahui kecepatan dan posisi partikel sebelum membuka pintu untuk seleksi?

Misalkan iblis itu tidak bisa mengukur kecepatan partikel yang menghantam pintu, mengapa? karena itu akan mengubah kecepatan partikel, jadi iblis harus mencari tahu sebelum membukanya, tanpa melihat, tanpa mengukur. Agar adil, kami akan membiarkan iblis mengetahui aturan permainan di muka, yaitu memberi makan iblis dengan hukum gerak, interaksi partikel, dan kondisi awal, cukup dengan model fisika / dinamis.

Tahap kedua

Sekarang memodelkan gas partikel juga sebagai program komputer yang menjalankan kode yang sama yang diberikan kepada setan untuk setiap partikel, sehingga gas menghitung hasil dari kondisi awalnya, Setan tidak tahu hasil itu sampai berhenti (jika pernah ): yaitu "partikel dengan kecepatan yang tepat ada di pintu", keputusan ya / tidak pertanyaan yang kita tanyakan ke sistem adalah "Apakah partikel memiliki posisi yang tepat dan kecepatan yang cukup?", jika demikian, pintu dapat dibuka dan partikel cepat dapat masuk ke sisi suhu tinggi ruangan menetapkan kondisi awal baru (akankah masalah berturut-turut itu memiliki jawaban? atau akan berjalan selamanya?)

Akan ada waktu ketika tidak ada partikel dengan kecepatan yang cukup untuk melewati batas, jadi, akan ada waktu ketika kode akan berjalan selamanya (jangan berhenti) untuk hampir semua ambang batas yang diberikan.

Setan ingin mengetahui hasil yang dihitung oleh gas, tetapi hasilnya dalam arti tertentu berpotensi terlibat dalam kode sumber hukum partikel ditambah kondisi awal .. tentu saja kita perlu menjalankan program itu untuk mengetahuinya. Jika Demon menjalankan program yang sama menunggu kecepatan yang tepat pada output, program tersebut dapat berhenti atau bisa berjalan selamanya (tapi kami juga mengira iblis tidak memiliki kekuatan komputasi lebih dari gas, sehingga tidak akan dapat memutuskan pintu terbuka tepat waktu).

Daemon dapat mencoba mencari tahu output program (atau jika itu akan berhenti) dengan menonton sumber dan input tanpa menjalankannya tetapi itu seperti mencoba untuk memecahkan Masalah Pemutusan, mengapa? karena Iblis tidak tahu apa hukum dan kondisi awal akan memberi makan sehingga Iblis harus siap untuk memecahkan setiap set hukum dan kondisi awal, dan kami tahu itu tidak mungkin secara umum, itu akan membutuhkan oracle, jika bisa itu akan cukup untuk membangun iblis untuk menghasilkan energi dari ketiadaan. (Bahkan mengetahui hukum dan kondisi awal, kedua hal itu sudah cukup sulit untuk diketahui)

Eksperimen pemikiran ini dapat menghubungkan bagaimana pengurangan entropi, melalui komputer, dapat dengan cara tertentu dibatasi oleh Halting Problem , sebagai masalah untuk mengantisipasi hasil secara umum.

(Kadang-kadang semua batas tampaknya menjadi batas yang sama ..)

Lebih lanjut tentang Hukum Partikel

Hukum partikel bukanlah masalah utama dari eksperimen pemikiran ini, hukum-hukum itu bisa kuantum atau klasik, tetapi kita harus memperhitungkan fakta kompleksitas hukum dan kondisi awal, kompleksitas susunan partikel tidak dibatasi, dan itu bisa memiliki banyak kompleksitas tambahan (dalam contoh ekstrim kondisi awal Anda bahkan dapat memasukkan seluruh partikel yang ditembakkan komputer sesuai dengan kode sumber internal dan memberikan kode tersebut ke daemon).

Pertanyaan yang sangat menawan, dan kami akan melihat bahwa pemikiran Anda benar .

Pertama mari kita lihat apa kata prinsip termodinamika kedua.

Fungsi entropi digunakan dalam hukum ke-2 termodinamika. Ini berasal dari teorema Carnot yang menyatakan bahwa proses yang terjadi di mesin uap memiliki efisiensi lebih rendah atau paling tidak sama dengan mesin "reversibel" yang sesuai (yang omong-omong seperti konsep yang tidak stabil selama 150 tahun termodinamika). Carnot tidak membuat koin fungsi entropi sendiri, tetapi bersama dengan Clausius inilah yang mereka katakan:

Karena tidak ada mesin perpetuum, maka kita dapat membangun fungsi S yang disebut entropi yang membatasi ukuran termodinamika makroskopik ke dalam persamaan tertentu, yaitu S (V, T, P, dll.) = 0

Perhatikan bahwa persamaan ini tidak lain adalah persamaan permukaan-hiper dalam ruang langkah-langkah termodinamika.

Memasuki Carathéodory.

Carathéodory adalah ahli matematika Jerman dan seperti semua ahli matematika lainnya, ia ingin mengekstraksi Carnot's dan Clausius dengan alasan beberapa aksioma yang akan memungkinkannya untuk menjelaskan apa sebenarnya hukum kedua itu. Terus terang dia ingin memurnikan termodinamika untuk mengetahui apa itu entropi.

Setelah mendaftarkan sejumlah aksioma, ia berhasil merumuskan hukum kedua HIS, yang mengatakan (kurang lebih):

ADA beberapa proses adiabatik. Atau lebih tepatnya, jika Anda ingin kembali, kadang-kadang bekerja sendiri tidak cukup. Anda perlu sedikit panas.

Sekarang sepertinya SANGAT berbeda dari formulasi Clausius! Tapi ternyata tidak. Yang dilakukan Carathéodory hanyalah mengubah urutan kata-kata, agak seperti ahli matematika yang bermain dengan aksioma ke-5 Euclide selama 2.000 tahun dan menghasilkan banyak kata yang berbeda untuk aksioma itu. Dan jika Anda mundur selangkah, Anda seharusnya tidak terlalu terkejut dengan pernyataan Carathéodory tentang hukum kedua. Faktanya, Carathéodory mengarah ke fungsi entropi yang sama dan persamaan hyper-surface S (V, T, P, dll.) = 0

Berpikir keras pada teorema Carnot. Sebagai ahli matematika, Anda tidak boleh terlalu puas dengan cara Carnot mengakui mesin perpetuum tidak ada. Bahkan, sebagai ahli matematika Anda lebih suka melihat sesuatu seperti ini:

Ada fungsi entropi S yang membatasi ukuran makroskopik JIKA DAN HANYA JIKA tidak ada mesin perpetuum ".

SEKARANG Anda memiliki teorema. Dan apa isinya? Bahwa selama tidak ada sistem mekanis terisolasi yang menghasilkan energi dalam jumlah tak terbatas dan karenanya dapat mengarahkan Anda ke keadaan apa pun yang Anda inginkan, maka Anda akan menemukan fungsi entropi. Sistem mekanik yang terisolasi adalah proses adiabatik. Karenanya, perumusan Carathéodory: tidak ada sistem adiabatik yang dapat menuntun Anda ke mana pun. Terkadang Anda membutuhkan panas.

Jadi tidak hanya kami yakin bahwa Carathéodory sudah benar, tetapi juga bahwa formulasinya cukup sederhana.

Sekarang dari mana Anda mendapatkan kesan bahwa hukum kedua à la Carathéodory mirip dengan masalah penghentian?

Ambil langkah mundur ke pernyataan Carathéodory. Yang dikatakannya adalah bahwa sekali Anda memiliki sistem mekanis terisolasi yang Anda hentikan berbaur, Anda tidak dapat mencapai kondisi apa pun yang Anda inginkan.

Bukankah itu kedengarannya seperti masalah terputus-putus? Yaitu begitu Anda telah menulis semua aksioma teori Anda dan meletakkan semua transisi yang mungkin, akan ada masalah yang tidak dapat Anda pecahkan. Terkadang, Anda perlu menambahkan lebih banyak aksioma.

Bahkan jika Anda ingin masuk sangat dalam dan menyandikan formulasi Carathéodory, ini akan menghasilkan kode yang sama dengan masalah penghentian dengan proses adiabatik alih-alih mesin Turing, dan menyatakan alih-alih masalah.

Apa yang kamu pikirkan?

CATATAN: Saya mengedit jawaban saya hampir seluruhnya sehingga komentar di bawah tidak akan sesuai dengan apa yang ada di dalamnya sekarang.