Что такое объем информации?

33

Этот вопрос был задан Жанетт Уинг после ее презентации PCAST по информатике.

«С точки зрения физики, есть ли максимальный объем информации, который мы можем иметь?» (Хороший вопрос для теоретического сообщества информатики, так как я думаю, что возникает вопрос «Что такое информация?»)

За пределами "Что такое информация?" Нужно также выяснить, что означает «объем» в этом контексте? Возможно, максимальная плотность информации является лучшей мерой.

Лэнс Фортноу
источник
1
Я понизил голосование, потому что я не нахожу этот вопрос релевантным для сайта (несмотря на то, насколько он бесконечно интересен). Насколько я могу судить, это действительно не соответствует требованиям в FAQ. Не ненавижу, Лэнс: я люблю твой блог и надеюсь когда-нибудь встретиться с тобой. Скажите Гасарху, извините, я еще не закончил рецензию на новости SIGACT. О_о Возможно, если бы вопрос был распакован немножко? Я почти уверен, что физики используют энтропию (степень свободы) для определения «физической» информации.
Росс Снайдер
1
@Ross: я интерпретировал вопрос так: «есть ли физический предел тому, сколько информации мы упаковываем в область космоса?» С этой интерпретацией я думаю, что это хороший вопрос, и я уже слышал ответ на него, поэтому я знаю, что ответ существует.
Робин Котари
@Robin: В этом случае вопрос (хотя и законный и интересный) на самом деле не является вопросом TCS (и поэтому не уместен), а также не отвечает требованиям здесь ( meta.cstheory.stackexchange.com/questions/225 /… ) [См. Ответ, который уже дан ниже - быстрый запрос Google, включающий «физику», «информацию» и «объем», доставит вас в то же место].
Росс Снайдер
@ Росс: Физическая основа информации не TCS? Я думаю, что это лучше всего обсудить на мета ... Voilà, Scope: Могут ли вопросы быть слишком физическими для нас?
Чарльз Стюарт
Я согласен с Россом Снайдером и проголосовал за его закрытие как не по теме. Хотя вопрос звучит интересно, для меня он выглядит как вопрос физики в его нынешнем виде.
Цуёси Ито

Ответы:

24

Ланс, на самом деле есть теорема, которая дает границы для этого. Margolus-Левитин теорема ограничивает скорость вычислений с точки зрения плотности энергии. Есть хороший трюк, который затем можно сыграть: если локальная плотность энергии превышает определенный предел, образуется черная дыра, вызывающая горизонт событий, который по существу не позволит вам получить ответ, причинно отключив эту область пространства-времени от остальная часть вселенной. У Сета Ллойда есть хорошая статья, в которой используется этот трюк для оценки вычислительной мощности вселенной ( Phys. Rev. Lett. 88, 237901 (2002) , arXiv ).

Конечно, вы можете использовать аналогичные рассуждения в любой конечной области пространства-времени.

Джо Фитцсимонс
источник
22

Этот комментарий в ее статье не дает много контекста о том, какой ответ она может ожидать. Но, безусловно, это уже известный и почтенный вопрос, о котором многое уже известно. Страница Википедии по голографическому принципуимеет хороший обзор. Самым противоречивым в голографическом принципе является то, что он говорит, что информационная емкость региона должна быть пропорциональна его площади поверхности; если вы думаете о емкости информации с точки зрения количества крошечных устройств с двумя состояниями, которые вы можете упаковать, вы ожидаете, что ограничивающим фактором будет внутренний объем. Эта интуиция остается верной до определенного момента, но в конечном итоге концентрация массы-энергии, оставляя в стороне проблемы квантовой миниатюризации, становится настолько велика, что образуется черная дыра. Грубо говоря, с помощью небольшого пространственного анализа и того факта, что гравитация является законом обратных квадратов, ее радиус в квадрате (пропорционален площади поверхности) является соответствующей величиной здесь.

Пер Вогсен
источник
6
Вероятно, это лучшая «научно-популярная» статья, которую я читал по голографическому принципу: sufizmveinsan.com/fizik/holographic.html
arnab,
«То, что черная дыра образуется, не означает, что она не содержит никакой информации». На самом деле, она имеет максимальную энтропию для содержащегося в ней количества массы-энергии относительно посторонних.
В Vognsen
Пер: Я удалил свой комментарий, потому что он не сделал того, о чем я хотел сказать: я думаю, что нам нужно быть осторожными в том, какую физическую теорию мы используем, чтобы ответить на этот вопрос. У меня сложилось впечатление, что теория квантовой гравитации не считается устоявшейся, а теоретико-струнные концепции плотности информации, безусловно, нет. Хороший ответ на этот вопрос должен идти медленнее.
Чарльз Стюарт
Справедливо. Мое единственное намерение было направить спрашивающего к существующей литературе по физике в этой области.
Per Vognsen
1
Чарльз: Одна из сильных сторон голографического принципа заключается в том, что он не основан на конкретной теории или идеологии квантовой гравитации; считается лакмусовой бумажкой, что предложенные теории должны пройти примерно. Мои знания теории струн практически равны нулю, но мне сказали, что теоретики струн объясняют голографический принцип.
Per Vognsen
-4

Это интересный и несколько забавный вопрос, но он плохо сформулирован в его нынешнем виде.

Я возьму еще один удар / риск при ответе, надеясь, что для оценки потребуется исходная сложность и базовая / присущая «мягкая» двусмысленность вопроса, а также то, что, исходя из текущих литературных знаний, существует несколько возможных путей, но, возможно, нет »правильного ответа ».

Похоже, что основным вопросом являются «физические аналогии в информатике», одним из которых является том. Поэтому это сильно связано с этим другим вопросом Физика приводит к TCS?

Чтобы ответить на этот вопрос, я выберу несколько разных подходов, которые, я думаю, имеют смысл.


Во-первых, одним подходом, иногда используемым в физике и технике, является «анализ измерений».

В этом случае строго интерпретируется, объем в единицах «пространство» или «длина в кубе». (Хотя обратите внимание, что в физике иногда термин «пространство» измеряется в терминах длины или длины в кубе.)

О(N3)

О(N3)

О(Nс)


Другой подход к аналогии объема (и других физических величин) в TCS заключается в следующем, как обсуждалось в другом вопросе. Известно, что SAT имеет точку перехода, чрезвычайно аналогичную точке перехода в физике / термодинамике, которая происходит, например, с идеальными газами при сжатии из одной фазы в другую, например газом в жидкость. Это происходит при уменьшении объема (скажем, контейнера с газом). Теперь в SAT со случайными входами основными двумя параметрами по размеру ввода являются предложения и переменные. (Другим параметром является количество переменных в предложениях, хотя это часто фиксируется на 3 для 3-SAT.)

Корректировка либо предложений, либо переменных при сохранении других фиксированных значений позволяет преодолеть сложность проблемы через точку перехода легко-трудно-легко. Поэтому кажется, что эти параметры чем-то аналогичны тому, хотя я не видел намеченных особенностей. Если углубиться в некоторые глубокие статьи по статистической физике SAT, может оказаться аналог тома. См. [5] для базового отображения SAT на терминологию статистической физики.

[5] Аналитическое и алгоритмическое решение задач случайной удовлетворенности. Мезард, Паризи, Зечина
http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf


Lп

Lп3

ВЗН
источник
ps Я разделю это на отдельные ответы, если есть поддержка, плз upvote этот комментарий, если вы согласны. Я также должен включить приемлемый в настоящее время ответ "нет смысла в объеме информации!" И вкратце
расскажу об