Complexidade

Minha postagem de ontem terminou com uma afirmação sobre o fato de haver programas de computador de diferentes graus de complexidade — isso era uma isca para alguém me perguntar como se mede complexidade. Mas já que ninguém mordeu o anzol, mordo-o eu mesmo! 🙂
Em seu livro sobre computação quântica (assunto já muito bem tratado no Universo Físico), Programming the Universe, Seth Lloyd pondera que medidas de complexidade geralmente tentam capturar o ponto de equilíbrio entre duas características de um sistema: o quanto é difícil descrevê-lo ou o quanto é difícil construí-lo. 
Ele passa pelos conceitos de complexidade termodinâmica (quantos bits são necessários para descrever precisamente um sistema) e complexidade algorítmica (qual o comprimento do menor programa de computador capaz de gerar uma descrição do sistema), mas nota que essas formulações medem informação bruta, não esforço ou estrutura.
LLoyd considera mais útil o conceito de complexidade computacional — o número de operações lógicas (AND, NOT, OR, COPY) envolvidas na geração de um resultado — e, mais útil ainda, o de profundidade lógica, ou o número de operações lógicas do menor programa capaz de gerar esse mesmo resultado.
Mas o conceito favorito é o que ele chama de complexidade profundidade termodinâmica, ou negentropia : o número de bits relevantes para a construção de um sistema. “Relevantes”, no caso, são os bits que, se alterados, fariam do sistema uma outra coisa. Por exemplo, a posição exata de cada átomo de carbono em meu corpo não é relevante pra eu ser o que (e quem) sou, mas o padrão geral em que eles estão organizados e a posição das bases do DNA no núcleo de minhas células são, claro, fundamentais.
Ou: a posição exata de cada molécula de oxigênio nesta sala não é importante, mas a pressão, a composição e a temperatura do ar, são. 
Assim: um sistema que requer muita informação para ser reconhecido como aquilo que é (um ser humano, um elefante, um nave espacial) tem alta profundidade termodinâmica; já um sistema que, embora tenha muita informação (as moléculas de ar nesta sala, cada uma com sua composição química, posição e velocidade), poderia continuar sendo exatamente o que é (uma massa de ar preenchendo a sala), mesmo se boa parte dessa informação mudasse, é termodinamicamente “raso”.
Isso gera algumas questões interessantes sobre o grau de subjetividade –e de recursividade: em que nível o sistema está sendo analisado — que fica implícito no conceito de complexidade, mas essa é uma discussão ara outra hora…

Discussão - 3 comentários

  1. Gonzo disse:

    Um bom exemplo é o tamanho que os sistemas operacionais estão tomando para serem o que são.
    Quem lembra por exemplo do Windows 3.1, 7 disquetes de 1,44MB.
    Desde este ponto foi descoberta tantas falhas, e feitos tantos aperfeiçoamentos nos códigos que hoje Windows Vista tem quase 4GB. Tem tanto driver pra cada modelo de hardware lançado desde então que a complexidade é gigante, e irrelevância deles também.
    Saudades das telas azuis da morte... 🙁

  2. Júlio disse:

    existe alguma forma (heurística ou algoritmo) pra encontrar essa profundidade termodinâmica? saber qual o número mínimo e quais os bits que alterados modificariam um sistema? ou só dá pra chegar a aproximações pela intuição mesmo?

  3. cretinas disse:

    Boa pergunta. Eu teria de estudar a questão mais a fundo pra responder com certeza, mas suponho que o conceito seja largamente intuitivo, mesmo -- embora talvez possa ser aproximado pelo de complexidade efetiva, que mede as regularidades de um sistema.
    Mas a aplicação da profundidade termodinâmica depende muito de em que nível o sistema está sendo analisado -- por exemplo, a humanidade pode ser estudada em grau ecológico, sociológico, psicológico ou biológico, e o que é relevante numa escala não é, necessariamente, relevante na outra.

Envie seu comentário

Seu e-mail não será divulgado. (*) Campos obrigatórios.

Categorias

Sobre ScienceBlogs Brasil | Anuncie com ScienceBlogs Brasil | Política de Privacidade | Termos e Condições | Contato


ScienceBlogs por Seed Media Group. Group. ©2006-2011 Seed Media Group LLC. Todos direitos garantidos.


Páginas da Seed Media Group Seed Media Group | ScienceBlogs | SEEDMAGAZINE.COM