Was ist das Informationsvolumen?

33

Diese Frage wurde Jeannette Wing nach ihrem PCAST-Vortrag über Informatik gestellt.

"Gibt es aus physikalischer Sicht ein maximales Informationsvolumen?"

Jenseits von "Was ist Information?" sollte man auch herausfinden, was "volumen" in diesem zusammenhang bedeutet? Vielleicht ist die maximale Informationsdichte ein besseres Maß.

Lance Fortnow
quelle
1
Ich habe einen Downvot durchgeführt, weil ich diese Frage für die Site nicht relevant finde (obwohl sie unendlich interessant ist). Soweit ich das beurteilen kann, entspricht es wirklich nicht den Qualifikationen in den FAQ. Kein Hass, Lance: Ich liebe deinen Blog und hoffe, dich eines Tages zu treffen. Sag Gasarch, dass es mir leid tut, dass ich die Buchbesprechung für SIGACT-News noch nicht abgeschlossen habe. O_o Vielleicht, wenn die Frage ein bisschen ausgepackt wäre? Ich bin mir ziemlich sicher, dass Physiker, die Entropie (Freiheitsgrade) verwenden, "physikalische" Informationen bestimmen.
Ross Snider
1
@ Ross: Ich interpretierte die Frage als "Gibt es eine physikalische Grenze für die Menge an Informationen, die wir in eine Raumregion packen?" Bei dieser Interpretation denke ich, dass es eine gute Frage ist, und ich habe bereits eine Antwort darauf gehört, sodass ich weiß, dass es eine Antwort gibt.
Robin Kothari
@Robin: In diesem Fall ist die Frage (obwohl legitim und interessant) nicht wirklich eine TCS-Frage (und daher nicht angemessen) und erfüllt auch nicht die hier angegebene Qualifikation ( meta.cstheory.stackexchange.com/questions/225) /… ) [Siehe die bereits unten gegebene Antwort - eine schnelle Google-Abfrage mit "Physik", "Informationen" und "Volumen" bringt Sie an den gleichen Ort].
Ross Snider
@ Ross: Die physikalische Basis der Information ist nicht TCS? Ich denke, dies wird am besten auf meta diskutiert ... Voilà, Scope: Können Fragen für uns zu physisch sein?
Charles Stewart
Ich stimme Ross Snider zu und habe dafür gestimmt, das Thema als "Off Topic" zu schließen. Während sich die Frage interessant anhört, sieht sie für mich in ihrer aktuellen Form wie eine physikalische Frage aus.
Tsuyoshi Ito

Antworten:

24

Lance, es gibt in der Tat einen Satz, der dem Grenzen setzt. Das Margolus-Levitin-Theorem begrenzt die Berechnungsrate in Bezug auf die Energiedichte. Es gibt einen schönen Trick, der gespielt werden kann: Wenn die lokale Energiedichte eine bestimmte Grenze überschreitet, bildet sich ein Schwarzes Loch, das einen Ereignishorizont erzeugt, der Sie im Wesentlichen daran hindert, eine Antwort zu erhalten, indem Sie diesen Raum-Zeit-Bereich kausal von dem trennen Rest des Universums. Seth Lloyd hat eine gute Arbeit, die diesen Trick verwendet, um die Rechenleistung des Universums abzuschätzen ( Phys. Rev. Lett. 88, 237901 (2002) , arXiv ).

Sie können natürlich eine ähnliche Argumentation für jede endliche Region der Raumzeit anwenden.

Joe Fitzsimons
quelle
22

Dieser Kommentar in ihrem Artikel gibt nicht viel Aufschluss darüber, welche Art von Antwort sie erwartet. Aber sicherlich ist dies inzwischen eine bekannte und ehrwürdige Frage, über die bereits viel bekannt ist. Die Wikipedia-Seite zum holographischen Prinziphat einen guten Überblick. Das Holografischste an diesem Prinzip ist, dass es besagt, dass die Informationskapazität einer Region proportional zu ihrer Oberfläche sein sollte. Wenn Sie an die Informationskapazität denken, wie viele winzige Geräte mit zwei Zuständen Sie dort einbauen können, würden Sie erwarten, dass das Innenvolumen der begrenzende Faktor ist. Diese Intuition gilt bis zu einem gewissen Punkt, aber schließlich wird die Konzentration von Massenenergie, abgesehen von Quantenminiaturisierungsproblemen, so groß, dass sich ein Schwarzes Loch bildet. Grob gesagt ist der Radius im Quadrat (proportional zur Oberfläche) nach Maßanalyse und der Tatsache, dass die Schwerkraft ein inverses Quadratgesetz ist, hier die relevante Größe.

Per Vognsen
quelle
6
Dies ist wahrscheinlich die besten „populäre Wissenschaft“ Artikel , den ich auf dem holografischen Prinzip gelesen habe: sufizmveinsan.com/fizik/holographic.html
arnab
"Dass sich ein Schwarzes Loch bildet, bedeutet nicht, dass es keine Informationen enthält." Tatsächlich hat es die maximale Entropie für seine enthaltene Menge an Massenenergie im Vergleich zu Außenstehenden.
Per Vognsen
Per: Ich habe meinen Kommentar gelöscht, weil er nicht zu dem von mir gewünschten Ergebnis geführt hat. Ich denke, wir müssen vorsichtig sein, auf welche physikalische Theorie wir uns stützen, um diese Frage zu beantworten. Ich habe den Eindruck, dass die Theorie der Quantengravitation nicht als festgelegt angesehen wird, und string-theoretische Konzepte der Informationsdichte sicherlich nicht. Eine gute Antwort auf diese Frage sollte langsamer erfolgen.
Charles Stewart
Meinetwegen. Meine einzige Absicht war es, den Fragesteller auf die existierende physikalische Literatur in diesem Bereich hinzuweisen.
Per Vognsen
1
Charles: Eine der Stärken des holographischen Prinzips ist, dass es nicht auf einer bestimmten Theorie oder Ideologie der Quantengravitation basiert. Es ist ein Lackmustest, den vorgeschlagene Theorien ungefähr bestehen sollten. Mein Wissen über die Stringtheorie ist praktisch gleich Null, aber mir wurde gesagt, dass Stringtheoretiker das holographische Prinzip berücksichtigt haben.
Per Vognsen
-4

Dies ist eine interessante und etwas amüsante Frage, die jedoch in der aktuellen Form schlecht formuliert ist.

Bei einer Antwort gehe ich ein weiteres Risiko ein und hoffe, dass die Bewertung die ursprüngliche Schwierigkeit und die grundlegende / inhärente "weiche" Mehrdeutigkeit der Frage berücksichtigt und dass es auf der Grundlage des aktuellen Literaturwissens mehrere mögliche Wege gibt, aber möglicherweise keine "richtige Antwort" ".

Die Hauptfrage scheint "Physikalische Analogien in der Informatik" zu sein, zu denen auch das Volumen gehört. Daher ist es in hohem Maße mit dieser anderen Frage verbunden. Physik führt zu TCS?

Um diese Frage zu beantworten, werde ich ein paar verschiedene Ansätze verfolgen, von denen ich denke, dass sie alle verdient haben.


Erstens ist ein Ansatz, der manchmal in den Bereichen Physik und Ingenieurwesen verwendet wird, die "dimensionale Analyse".

In diesem Fall wird das Volumen streng interpretiert in der Einheit "Raum" oder "Länge gewürfelt". (Obwohl der Begriff "Raum" in der Physik manchmal entweder in Länge oder in Würfellänge gemessen wird.)

O(n3)

O(n3)

O(nc)


Ein anderer Ansatz für eine Volumenanalogie (und andere physikalische Größen) in TCS lautet wie folgt, wie in der anderen Frage erörtert. Es ist bekannt, dass SAT einen Übergangspunkt hat, der dem Übergangspunkt in der Physik / Thermodynamik sehr ähnlich ist, was z. B. bei idealen Gasen unter Kompression von einer Phase zu einer anderen geschieht, z. B. von Gas zu Flüssigkeit. Dies geschieht unter einer Volumenverringerung (etwa des Gasbehälters). In SAT mit zufälligen Eingaben sind die beiden wichtigsten Parameter für die Eingabegröße Klauseln und Variablen. (Ein weiterer Parameter ist die Anzahl der Variablen in Klauseln, obwohl diese für 3-SAT häufig auf 3 festgelegt ist.)

Wenn Sie entweder die Klauseln oder Variablen anpassen, während Sie die andere festhalten, wird die Schwierigkeit des Problems durch den Übergangspunkt "leicht-schwer-leicht" verschoben. Daher scheinen diese Parameter irgendwie analog zu Volume zu sein, obwohl ich die Einzelheiten nicht herausgearbeitet habe. Ein Blick in einige der tiefgründigen Arbeiten zur statistischen Physik von SAT kann das Analogon von Volume aufdecken. Siehe [5] für eine grundlegende Zuordnung von SAT zur Terminologie der statistischen Physik.

[5] Analytische und algorithmische Lösung zufälliger Zufriedenheitsprobleme von Mezard, Parisi, Zechina
http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf


lp

lp3

vzn
quelle
ps Ich werde dies in separate Antworten aufteilen, wenn es Unterstützung gibt. Bitte stimmen Sie diesem Kommentar zu, wenn Sie damit einverstanden sind. Ich soll auch die derzeit akzeptable Antwort schließen „gibt es keine Bedeutung für das Volumen an Informationen!“ & Argumentieren Sie diesen Fall kurz
vzn