Qual é o volume de informações?

33

Esta pergunta foi feita a Jeannette Wing após sua apresentação no PCAST sobre ciência da computação.

“Do ponto de vista da física, existe um volume máximo de informações que possamos ter?” (Uma boa pergunta de desafio para a comunidade teórica da ciência da computação, pois acho que ela implora a pergunta “O que é informação?”)

Além de "O que é informação?" deve-se também descobrir o que "volume" significa neste contexto? Talvez a densidade máxima de informações seja uma medida melhor.

Lance Fortnow
fonte
1
Fiz um voto negativo porque não acho essa pergunta relevante para o site (apesar de infinitamente interessante). Realmente não atende às qualificações das perguntas frequentes, até onde eu sei. Sem ódio, Lance: adoro o seu blog e espero um dia conhecê-lo. Diga a Gasarch que sinto muito por ainda não ter terminado a resenha do livro. O_o Talvez se a pergunta fosse descompactada um pouco? Tenho certeza de que as pessoas de física usam entropia (graus de liberdade) determinam informações "físicas".
Ross Snider
1
@ Ross: Eu interpretei a pergunta como "existe um limite físico para quanta informação empacotamos em uma região do espaço?" Com essa interpretação, acho que é uma boa pergunta, e já ouvi uma resposta antes, então sei que existe uma resposta.
Robin Kothari
@ Robin: nesse caso, a pergunta (embora legítima e interessante) não é realmente uma pergunta do TCS (e, portanto, não é apropriada), e também não atende à qualificação aqui ( meta.cstheory.stackexchange.com/questions/225) /… ) [Veja a resposta já fornecida abaixo - uma consulta rápida do Google envolvendo "física" "informações" e "volume" levará você ao mesmo lugar].
Ross Snider
@ Ross: A base física da informação não é a TCS? Eu acho que isso é melhor discutido na meta ... Voilà, Scope: As perguntas podem ser muito físicas para nós?
Charles Stewart
Eu concordo com Ross Snider e votei para fechá-lo como fora de tópico. Embora a pergunta pareça interessante, ela me parece uma questão de física em sua forma atual.
Tsuyoshi Ito

Respostas:

24

Lance, de fato, existe um teorema que dá limites a isso. O teorema de Margolus-Levitin limita a taxa de computação em termos de densidade de energia. Existe um bom truque que pode ser executado: se a densidade de energia local exceder um certo limite, um buraco negro se formará causando um horizonte de eventos que essencialmente impedirá que você obtenha uma resposta desconectando causalmente essa região do espaço-tempo da região. resto do universo. Seth Lloyd tem um bom artigo usando esse truque para estimar o poder computacional do universo ( Phys. Rev. Lett. 88, 237901 (2002) , arXiv ).

É claro que você pode usar raciocínio semelhante em qualquer região finita do espaço-tempo.

Joe Fitzsimons
fonte
22

Esse comentário em seu artigo não fornece muito contexto sobre que tipo de resposta ela pode estar esperando. Mas certamente essa é agora uma pergunta bem conhecida e venerável sobre a qual muito já se sabe. A página da Wikipedia sobre o princípio holográficotem uma boa visão geral. A coisa mais contra-intuitiva sobre o princípio holográfico é que ele diz que a capacidade de informação de uma região deve ser proporcional à sua área de superfície; se você pensar na capacidade de informação em termos de quantos dispositivos minúsculos de dois estados pode levar, esperaria que o volume interior fosse o fator limitante. Essa intuição é verdadeira até certo ponto, mas, eventualmente, a concentração de energia em massa, deixando de lado os problemas de miniaturização quântica, torna-se tão grande que um buraco negro se forma. Grosso modo, por um pouco de análise dimensional e pelo fato de a gravidade ser uma lei do quadrado inverso, seu raio ao quadrado (proporcional à área da superfície) é a quantidade relevante aqui.

Per Vognsen
fonte
6
Este é provavelmente o melhor artigo de "ciência popular" que li sobre o princípio holográfico: sufizmveinsan.com/fizik/holographic.html
arnab
"O fato de um buraco negro se formar não significa que ele não contém informações" De fato, possui entropia máxima para sua quantidade contida de energia em massa, em relação a pessoas de fora.
Por Vognsen
Por: eu apaguei meu comentário, porque não fez o ponto que eu queria enfatizar, que é que acho que precisamos ter cuidado com a teoria física que adotamos para responder a essa pergunta. Tenho a impressão de que a teoria da gravidade quântica não é considerada estabelecida, e os conceitos teóricos das cordas de densidade da informação certamente não são. Uma boa resposta para essa pergunta deve prosseguir em um ritmo mais lento.
Charles Stewart
Justo. Minha única intenção era apontar o questionador para a literatura física existente nessa área.
Por Vognsen
1
Charles: Um dos pontos fortes do princípio holográfico é que ele não se baseia em uma teoria ou ideologia específica da gravidade quântica; é considerado um teste decisivo que as teorias propostas devem passar aproximadamente. Meu conhecimento da teoria das cordas é praticamente nulo, mas me disseram que os teóricos das cordas foram responsáveis ​​pelo princípio holográfico.
Por Vognsen 23/09/10
-4

Essa é uma pergunta interessante e um tanto divertida, mas mal formulada em sua forma atual.

Vou tomar outra facada / risco em uma resposta, esperando que a pontuação leve em consideração a dificuldade original e a ambiguidade "suave" básica / inerente da pergunta, e que, com base no conhecimento atual da literatura, existem vários caminhos possíveis, mas sem dúvida nenhuma "resposta correta" "

A questão principal parece ser "analogias da física na ciência da computação", cujo volume é uma delas. Portanto, está altamente relacionado a essa outra pergunta que a física resulta no TCS?

Para responder a essa pergunta, adotarei algumas abordagens diferentes, que acho que todas têm mérito.


primeiro, uma abordagem às vezes usada nos campos da física e da engenharia é a "análise dimensional".

Nesse caso, estritamente interpretado, o volume está na unidade "espaço" ou "comprimento em cubo". (Embora a nota na física às vezes o termo "espaço" seja medido em termos de comprimento ou comprimento em cubos.)

O(n3)

O(n3)

O(nc)


Outra abordagem para uma analogia de volume (e outras quantidades físicas) no TCS é a seguinte, conforme discutido na outra questão. Sabe-se que o SAT possui um ponto de transição extremamente análogo ao ponto de transição na física / termodinâmica, o que acontece, por exemplo, com gases ideais sob compressão de uma fase para outra, por exemplo, gás para líquido. Isso acontece com uma diminuição no volume (digamos, no contêiner do gás). Agora, no SAT com entradas aleatórias, os dois principais parâmetros no tamanho da entrada são cláusulas e variáveis. (Outro parâmetro é o número de variáveis ​​em cláusulas, embora isso geralmente seja fixado em 3 para 3-SAT.)

Ajustar as cláusulas ou variáveis, mantendo a outra fixa, empurra a dificuldade do problema pelo ponto de transição fácil-difícil-fácil. Portanto, parece que esses parâmetros são de alguma forma análogos ao Volume, embora eu não tenha visto os detalhes mapeados. Investigar alguns dos trabalhos mais aprofundados sobre a física estatística do SAT pode transformar o análogo do Volume. Veja [5] para um mapeamento básico do SAT na terminologia estatística da física.

[5] Solução analítica e algorítmica de problemas de confiabilidade aleatória de Mezard, Parisi, Zechina
http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf


lp

lp3

vzn
fonte
ps Vou dividir isso em respostas separadas, se houver suporte, por favor, vote este comentário se você concorda. Também devo incluir a resposta atualmente aceitável "não há significado para o volume de informações!" & argumentar esse caso brevemente
vzn 14/01/12