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.

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.

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ą.

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ść.

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^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$