Jaka jest objętość informacji?

To pytanie zostało zadane Jeannette Wing po prezentacji PCAST na temat informatyki.

„Czy z punktu widzenia fizyki istnieje maksymalna ilość informacji, którą możemy mieć?” (Fajne wyzwanie dla teoretycznej społeczności informatycznej, ponieważ myślę, że rodzi to pytanie „Czym jest informacja?”)

Poza „Czym jest informacja?” należy również dowiedzieć się, co oznacza „objętość” w tym kontekście? Być może lepszym miernikiem jest maksymalna gęstość informacji.

it.information-theory physics

— Lance Fortnow
źródło

Zgłosiłem się negatywnie, ponieważ nie uważam tego pytania za istotne dla witryny (pomimo tego, jak nieskończenie interesujące jest). O ile mi wiadomo, to naprawdę nie spełnia wymagań zawartych w FAQ. Bez nienawiści, Lance: Uwielbiam twojego bloga i pewnego dnia mam nadzieję cię poznać. Powiedz Gasarchowi, że przepraszam, że nie skończyłem jeszcze przeglądu książki dla nowości SIGACT. O_o Może gdyby to pytanie zostało trochę rozpakowane? Jestem prawie pewien, że fizycy używający entropii (stopnie swobody) określają informacje „fizyczne”.

— Ross Snider,

@ Ross: Zinterpretowałem to pytanie jako „czy istnieje fizyczny limit ilości informacji, które pakujemy w region kosmiczny?” Przy tej interpretacji myślę, że to dobre pytanie, i słyszałem już wcześniej odpowiedź, więc wiem, że odpowiedź istnieje.

— Robin Kothari,

@Robin: W takim przypadku pytanie (choć uzasadnione i interesujące) nie jest tak naprawdę pytaniem TCS (a więc nie jest właściwe), a także nie spełnia tutaj kwalifikacji ( meta.cstheory.stackexchange.com/questions/225 /… ) [Patrz odpowiedź już podana poniżej - szybkie zapytanie Google zawierające „informacje fizyczne”, „informacje” i „objętość” przeniesie Cię w to samo miejsce].

— Ross Snider,

@Ross: Fizyczną podstawą informacji nie jest TCS? Myślę, że najlepiej to omawiać na stronie meta ... Voilà, Zakres: Czy pytania mogą być dla nas zbyt fizyczne?

— Charles Stewart

Zgadzam się na Rossa Snidera i głosowałem za jego zamknięciem. Chociaż pytanie brzmi interesująco, dla mnie wygląda w fizyce w obecnej formie.

— Tsuyoshi Ito,

Odpowiedzi:

Lance, w rzeczywistości istnieje twierdzenie, które wyznacza granice tego. Twierdzenie Margolusa-Levitina ogranicza tempo obliczeń pod względem gęstości energii. Istnieje dobra sztuczka, którą można następnie zagrać: jeśli lokalna gęstość energii przekroczy określony limit, powstanie czarna dziura, powodując horyzont zdarzeń, który zasadniczo uniemożliwi uzyskanie odpowiedzi przez przypadkowe odłączenie tego obszaru czasoprzestrzeni od reszta wszechświata. Seth Lloyd ma niezłą gazetę wykorzystującą tę sztuczkę do oszacowania mocy obliczeniowej wszechświata ( Phys. Rev. Lett. 88, 237901 (2002) , arXiv ).

Możesz oczywiście zastosować podobne rozumowanie w dowolnym skończonym regionie czasoprzestrzeni.

— Joe Fitzsimons
źródło

Ten komentarz w jej artykule nie zawiera wielu kontekstów na temat tego, jakiej odpowiedzi może się spodziewać. Ale z pewnością jest to dobrze znane i czcigodne pytanie, o którym wiele już wiadomo. Strona Wikipedii na temat zasady holograficznejma dobry przegląd. Najbardziej sprzeczną z intuicją rzeczą w holograficznej zasadzie jest to, że mówi, że pojemność informacyjna regionu powinna być proporcjonalna do jego powierzchni; jeśli pomyśleć o pojemności informacyjnej w kategoriach liczby małych dwustanowych urządzeń, które można tam spakować, można oczekiwać, że wielkość wewnętrzna będzie czynnikiem ograniczającym. Ta intuicja obowiązuje do pewnego momentu, ale w końcu koncentracja masy i energii, odkładając na bok kwestie miniaturyzacji kwantowej, staje się tak wielka, że tworzy się czarna dziura. Z grubsza mówiąc, poprzez analizę wymiarów i fakt, że grawitacja jest prawem odwrotnych kwadratów, jej promień kwadratowy (proporcjonalny do pola powierzchni) jest tutaj odpowiednią wielkością.

— Per Vognsen
źródło

Jest to prawdopodobnie najlepszy artykuł „popularnonaukowy”, jaki przeczytałem na temat holograficznej zasady: sufizmveinsan.com/fizik/holographic.html

— arnab

„To, że tworzy się czarna dziura, nie oznacza, że nie zawiera żadnych informacji” W rzeczywistości ma maksymalną entropię dla zawartej ilości energii masowej w stosunku do osób postronnych.

— Per Vognsen,

Per: Usunąłem swój komentarz, ponieważ nie wskazał na to, co chciałem powiedzieć, a mianowicie, że uważam, że musimy uważać na to, jaką teorię fizyczną wciągamy, aby odpowiedzieć na to pytanie. Mam wrażenie, że teoria grawitacji kwantowej nie jest uważana za ustaloną, a teoretyczne koncepcje gęstości informacji na pewno nie. Dobra odpowiedź na to pytanie powinna przebiegać wolniej.

— Charles Stewart,

Słusznie. Moim jedynym zamiarem było skierowanie pytającego w kierunku istniejącej literatury fizyki w tej dziedzinie.

— Per Vognsen,

Charles: Jedną z mocnych stron holograficznej zasady jest to, że nie opiera się ona na określonej teorii lub ideologii kwantowej grawitacji; uważa się za test lakmusowy, że proponowane teorie powinny przejść w przybliżeniu. Moja wiedza na temat teorii strun jest praktycznie zerowa, ale powiedziano mi, że teoretycy strun tłumaczą holograficzną zasadę.

— Per Vognsen,

-4

To interesujące i nieco zabawne pytanie, ale w obecnej formie jest źle sformułowane.

Podejmę kolejne dźgnięcie / ryzyko przy odpowiedzi, mając nadzieję, że punktacja weźmie pod uwagę pierwotną trudność i podstawową / nieodłączną „miękką” dwuznaczność pytania i że w oparciu o aktualną wiedzę z literatury istnieje kilka możliwych dróg, ale prawdopodobnie nie „poprawna odpowiedź” „.

Głównym pytaniem wydaje się być „analogia fizyki w informatyce”, której tom jest jednym z nich. Dlatego jest to ściśle związane z tym drugim pytaniem Wyniki fizyki w TCS?

Aby odpowiedzieć na to pytanie, przyjmuję kilka różnych podejść, które moim zdaniem mają wartość.

po pierwsze, jednym podejściem stosowanym czasami w dziedzinie fizyki i inżynierii jest „analiza wymiarowa”.

W tym przypadku ściśle interpretowana objętość jest w jednostce „spacja” lub „długość w kostce”. (Chociaż uwaga w fizyce jest czasami określana jako „przestrzeń” mierzona albo w kategoriach długości, albo długości w kostkach).

$O(n^3)$

$O(n^c)$

Inne podejście do analogii objętości (i innych wielkości fizycznych) w TCS jest następujące, jak omówiono w innym pytaniu. Wiadomo, że SAT ma punkt przejścia niezwykle analogiczny do punktu przejścia w fizyce / termodynamice, co dzieje się np. Przy idealnych gazach pod ciśnieniem z jednej fazy do drugiej, np. Gaz do cieczy. Dzieje się tak przy spadku objętości (powiedzmy o zbiorniku gazu). Teraz w SAT z losowymi wejściami głównymi dwoma parametrami wielkości wejściowej są klauzule i zmienne. (Kolejnym parametrem jest liczba zmiennych w klauzulach, chociaż często jest to ustalone na 3 dla 3-SAT.)

Dostosowanie klauzul lub zmiennych przy jednoczesnym zachowaniu drugiej stałej przepycha trudność problemu przez łatwy-trudny-łatwy punkt przejścia. Dlatego wydaje się, że parametry te są w jakiś sposób analogiczne do Volume, chociaż nie widziałem odwzorowania szczegółów. Zagłębiając się w niektóre z głębokich artykułów na temat fizyki statystycznej SAT, można podnieść analogię do tomu. Zobacz [5], aby zapoznać się z podstawowym mapowaniem SAT na terminologię fizyki statystycznej.

[5] Analityczne i algorytmiczne rozwiązanie problemów losowej satysfakcji autorstwa Mezarda, Parisi, Zechiny
http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf

$l_p$

$l_p^3$

— vzn
źródło

ps Podzielę to na osobne odpowiedzi, jeśli jest poparcie, proszę o głosowanie na ten komentarz, jeśli się zgadzasz. Powinienem również dołączyć obecnie akceptowalną odpowiedź „nie ma znaczenia ilość informacji!” i

— pokierujcie