Kompleksitas entropi dan komputasi

12

Ada peneliti yang menunjukkan bahwa menghapus bit harus mengkonsumsi energi, sekarang adakah penelitian yang dilakukan terhadap konsumsi rata-rata algoritma dengan kompleksitas komputasi ? Saya kira, kompleksitas komputasi F ( n ) berkorelasi dengan konsumsi energi rata-rata, harap saya bisa mendapatkan jawaban di sini.F(n)F(n)

cc.complexity-theory reference-request it.information-theory quantum-information statistical-physics XL _At_Here_There
sumber
Menautkan ke makalah yang dimaksud akan meningkatkan pertanyaan ini.
Stella Biderman
@StellaBiderman terima kasih, tetapi saya belum menemukan tautan di komentar Anda.
XL _At_Here_There
Saya tidak tahu makalah / peneliti apa yang Anda bicarakan. Saya menyarankan agar Anda memberikan I
Stella Biderman
1
@StellaBiderman Saya salah mengerti komentar Anda, sebenarnya saya baru saja membaca sebuah teks yang menyatakan "menghapus bit harus menghabiskan energi" dalam kompleksitas Kolmogorov dan penerapannya oleh Viatanyi dan Li. Saya pikir saya belum membaca artikel dan buku terkait lainnya
XL _At_Here_There

Jawaban:

16

Ya, tetapi sebagian besar pekerjaan sejauh ini (kecuali baru-baru ini, lihat di bawah) telah berfokus pada mengubah perhitungan yang tidak dapat diubah menjadi yang reversibel, dengan demikian berharap untuk menghindari generasi entropi. (Catatan: ada perbedaan penting antara energi yang dibutuhkan untuk menjalankan komputasi, dan entropi yang dihasilkan oleh komputasi dan dikeluarkan ke lingkungan, biasanya dalam bentuk panas.)

kTln⁡(2)

Baru-baru ini,

Demaine, Lynch, Mirano, dan Tyagi. Algoritma Hemat Energi , 2016.

mempelajari sebagian algoritma yang dapat dibalik - yaitu, jika Anda bersedia membayar beberapa entropi, untuk tugas algoritmik standar dapat ditingkatkan dengan simulasi ireversibel-ke-reversibel umum yang disebutkan di atas. Komputasi reversibel memiliki seluruh komunitas peneliti yang dikhususkan untuk itu, yaitu. yang Reversible Computing konferensi, sekarang di tahun ke-10.

ln⁡(2)

Kolchinsky & Wolpert, Ketergantungan disipasi pada distribusi awal atas negara . J. Stat. Mech. 2017 ( tautan arXiv )

(dan referensi di dalamnya).

Kami menjadi tuan rumah sebuah lokakarya tentang hal ini di Santa Fe Institute pada Agustus 2017 (di mana Anda dapat melihat nama-nama beberapa peneliti dan judul pembicaraan yang relevan), dan itu menimbulkan serangkaian pertanyaan baru dalam kompleksitas fisika dan komputasi termodinamika.

Joshua Grochow
sumber
Mesin Turing atau Turing Gereja-Turing dapat dikuasai atau dibatasi oleh hukum fisik, sehingga kemungkinan apakah komputasi kuantum atau komunikasi kuantum dapat diimplementasikan dapat disimpulkan dari hukum fisika, seperti hukum kedua mekanika statistik, relativitas umum. Jadi saya kira jika ada hasil tentang hubungan tesis dan hukum fisika
XL _At_Here_There
Dan sepertinya situs fisika tidak tertarik dengan topik semacam ini.
XL _At_Here_There
@XL_at_China: Ada "tesis Turing Gereja Fisik", tapi ini tidak ada hubungannya dengan hukum kedua, karena tesis Gereja Turing dan versi fisiknya hanya tentang apa yang dapat dihitung, bukan tentang segala jenis perkiraan kuantitatif , tetapi hukum kedua adalah pernyataan kuantitatif. Juga, walaupun mungkin belum ada satu ton publikasi tentang itu, di bengkel kami para fisikawan tampaknya tertarik.
Joshua Grochow
Saya telah mencoba menemukan hubungan beberapa tahun yang lalu, tetapi gagal mendapatkan hasil apa pun. Secara intuitif, komputabilitas tampaknya harus dikaitkan dengan hukum termodinamika kedua. Dan mempertimbangkan Turing Machine dalam istilah relativitas umum, masalahnya menjadi menarik. Tapi saya tidak tahu ada fisikawan yang tertarik dengan masalah seperti itu.
XL _At_Here_There
Dan bisakah kita mengirim pertanyaan terkait pada fisika situs, dan mendiskusikannya dengan fisikawan?
XL _At_Here_There