Apa Volume Informasi?

Pertanyaan ini diajukan kepada Jeannette Wing setelah presentasi PCAST tentang ilmu komputer.

"Dari perspektif fisika, apakah ada volume maksimum informasi yang dapat kita miliki?" (Pertanyaan tantangan yang bagus untuk komunitas ilmu komputer teoretis karena saya pikir itu menimbulkan pertanyaan "Apa itu informasi?")

Melampaui "Apa itu informasi?" kita juga harus mencari tahu apa arti "volume" dalam konteks ini? Mungkin kepadatan informasi maksimum adalah ukuran yang lebih baik.

it.information-theory physics Lance Fortnow
sumber

Saya downvoted karena saya tidak menemukan pertanyaan ini relevan dengan situs (meskipun betapa menariknya itu). Itu benar-benar tidak memenuhi kualifikasi di FAQ sejauh yang saya tahu. Tidak membenci, Lance: Saya suka blog Anda dan suatu hari nanti berharap untuk bertemu dengan Anda. Beri tahu Gasarch, saya minta maaf saya belum menyelesaikan ulasan buku untuk berita SIGACT. O_o Mungkin kalau pertanyaannya dibongkar sedikit? Saya cukup yakin orang fisika menggunakan entropi (derajat kebebasan) menentukan informasi "fisik".

Ross Snider

@Ross: Saya menafsirkan pertanyaan yang berarti "apakah ada batasan fisik untuk berapa banyak informasi yang kami masukkan ke dalam suatu wilayah ruang?" Dengan interpretasi itu, saya pikir itu adalah pertanyaan yang bagus, dan saya sudah pernah mendengar jawabannya, jadi saya tahu ada jawaban.

Robin Kothari

@Robin: Dalam hal ini pertanyaannya (meskipun sah dan menarik) sebenarnya bukan pertanyaan TCS (dan karenanya tidak sesuai), dan juga tidak memenuhi kualifikasi di sini ( meta.cstheory.stackexchange.com/questions/225 / ... ) [lihat jawaban yang sudah diberikan di bawah ini - permintaan Google yang cepat yang melibatkan "informasi" "fisika" dan "volume" akan membawa Anda ke tempat yang sama].

Ross Snider

@Ross: Basis fisik informasi bukan TCS? Saya pikir ini sebaiknya dibahas pada meta ... Voilà, Ruang Lingkup: Bisakah pertanyaan terlalu fisik bagi kita?

Charles Stewart

Saya setuju dengan Ross Snider dan memilih untuk menutupnya sebagai di luar topik. Sementara pertanyaannya terdengar menarik, sepertinya pertanyaan dalam fisika bagi saya dalam bentuk saat ini.

Tsuyoshi Ito

Jawaban:

Tombak, sebenarnya ada teorema yang memberi batasan pada ini. The Margolus-Levitin teorema batas tingkat perhitungan dalam hal kepadatan energi. Ada trik yang bagus yang dapat dimainkan: Jika kepadatan energi lokal melebihi batas tertentu, sebuah lubang hitam akan terbentuk menyebabkan cakrawala peristiwa yang pada dasarnya akan mencegah Anda mendapatkan jawaban dengan memutuskan secara konektifitas wilayah ruang-waktu dari sisa alam semesta. Seth Lloyd memiliki karya yang bagus menggunakan trik ini untuk memperkirakan kekuatan komputasi alam semesta ( Phys. Rev. Lett. 88, 237901 (2002) , arXiv ).

Tentu saja Anda dapat menggunakan alasan yang sama pada setiap wilayah ruang-waktu yang terbatas.

Joe Fitzsimons
sumber

Komentar dalam artikelnya itu tidak memberikan banyak konteks tentang jawaban seperti apa yang mungkin dia harapkan. Namun yang pasti sekarang ini adalah pertanyaan yang terkenal dan terhormat tentang yang sudah banyak diketahui. Halaman Wikipedia tentang prinsip holografikmemiliki ikhtisar yang baik. Hal yang paling berlawanan dengan prinsip holografik adalah bahwa ia mengatakan kapasitas informasi suatu daerah harus proporsional dengan luas permukaannya; jika Anda memikirkan kapasitas informasi dalam hal berapa banyak perangkat dua-negara kecil yang dapat Anda kemas di sana, Anda akan mengharapkan volume interior menjadi faktor pembatas. Intuisi itu berlaku hingga titik tertentu, tetapi akhirnya konsentrasi energi-massa, mengesampingkan masalah miniaturisasi kuantum, menjadi begitu besar sehingga sebuah lubang hitam terbentuk. Secara kasar, dengan sedikit analisis dimensi dan fakta bahwa gravitasi adalah hukum kuadrat terbalik, jari-jarinya kuadrat (sebanding dengan luas permukaan) itulah kuantitas yang relevan di sini.

Per Vognsen
sumber

Ini mungkin artikel "sains populer" terbaik yang pernah saya baca tentang prinsip holografik: sufizmveinsan.com/fizik/holographic.html

arnab

"Bahwa bentuk black hole tidak berarti tidak mengandung informasi" Faktanya, ia memiliki entropi maksimum untuk jumlah energi massa yang terkandung, relatif terhadap orang luar.

Per Vognsen

Per: Saya menghapus komentar saya, karena itu tidak membuat poin yang ingin saya sampaikan, yaitu saya pikir kita perlu berhati-hati tentang teori fisik apa yang kita tarik untuk menjawab pertanyaan ini. Saya memiliki kesan bahwa teori gravitasi quantum tidak dianggap sebagai mapan, dan konsep string-theoretic tentang kepadatan informasi tentu saja tidak. Jawaban yang bagus untuk pertanyaan ini harus dilanjutkan dengan langkah yang lebih lambat.

Charles Stewart

Cukup adil. Niat saya satu-satunya adalah mengarahkan penanya ke literatur fisika yang ada di bidang ini.

Per Vognsen

Charles: Salah satu kekuatan dari prinsip holografik adalah bahwa ia tidak didasarkan pada teori atau ideologi gravitasi kuantum tertentu; itu dianggap sebagai tes lakmus bahwa teori yang diajukan harus lulus sekitar. Pengetahuan saya tentang teori string hampir tidak ada, tetapi saya telah diberitahu bahwa ahli teori string telah menjelaskan prinsip holografik.

Per Vognsen

-4

Ini adalah pertanyaan yang menarik dan agak lucu tetapi dirumuskan dengan buruk dalam bentuk saat ini.

Saya akan mengambil tikaman / risiko lain pada jawaban yang berharap bahwa penilaian akan mengambil kesulitan asli dan ambiguitas "lunak" yang mendasar / inheren dari pertanyaan dalam pikiran dan bahwa berdasarkan pengetahuan literatur saat ini ada beberapa jalan yang mungkin tetapi tidak bisa dibilang "jawaban yang benar" ".

Permintaan utama tampaknya adalah "analogi fisika dalam ilmu komputer" yang volumenya adalah salah satunya. Oleh karena itu sangat terkait dengan pertanyaan lain ini. Hasil Fisika dalam TCS?

Untuk menjawab pertanyaan ini saya akan mengambil beberapa pendekatan berbeda yang menurut saya semua memiliki kelebihan.

pertama, satu pendekatan yang kadang-kadang digunakan dalam bidang fisika dan teknik adalah "analisis dimensi".

Dalam hal ini ditafsirkan secara ketat, volume adalah dalam unit "ruang" atau "panjang potong dadu". (Meskipun catatan dalam fisika kadang-kadang istilah "ruang" diukur dalam bentuk panjang atau panjang potong dadu.)

$O(n^3)$

$O(n^c)$

Pendekatan lain untuk analogi volume (dan jumlah fisika lainnya) dalam TCS adalah sebagai berikut, seperti yang dibahas dalam pertanyaan lain. Diketahui bahwa SAT memiliki titik transisi yang sangat analog dengan titik transisi dalam fisika / termodinamika, Yang terjadi misalnya dengan gas ideal di bawah kompresi dari satu fase ke fase lain, misalnya gas ke cairan. Ini terjadi di bawah penurunan volume (misalnya dari wadah gas). Sekarang di SAT dengan input acak dua parameter utama pada ukuran input adalah klausa dan variabel. (Parameter lain adalah jumlah variabel dalam klausa, meskipun itu sering diperbaiki pada 3 untuk 3-SAT.)

Menyesuaikan baik klausa atau variabel sambil tetap tetap lainnya mendorong kesulitan masalah melalui titik transisi mudah-sulit-mudah. Oleh karena itu sepertinya parameter ini entah bagaimana analog dengan Volume walaupun saya belum melihat spesifiknya dipetakan. Menggali ke dalam beberapa makalah yang mendalam tentang fisika statistik SAT dapat mengubah analog Volume. Lihat [5] untuk pemetaan dasar SAT ke terminologi fisika statistik.

[5] Solusi Analitik dan Algoritmik dari Masalah Kepuasan Acak oleh Mezard, Parisi, Zechina
http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf

$l_p$

$l_p^3$

ay
sumber

ps Saya akan membaginya menjadi jawaban yang terpisah jika ada dukungan, tunggulah komentar ini jika Anda setuju. Saya juga harus memasukkan jawaban yang saat ini dapat diterima, "tidak ada artinya dengan volume informasi!" &

bantah