Problema transcomputacional - Transcomputational problem

Na teoria da complexidade computacional , um problema transcomputacional é um problema que requer o processamento de mais de 10 93 bits de informação. Qualquer número maior que 10 93 é chamado de número transcomputacional . O número 10 93 , chamado de limite de Bremermann , é, de acordo com Hans-Joachim Bremermann , o número total de bits processados ​​por um computador hipotético do tamanho da Terra em um período de tempo igual à idade estimada da Terra. O termo transcomputacional foi cunhado por Bremermann.

Exemplos

Testando circuitos integrados

O teste exaustivo de todas as combinações de um circuito integrado com 309 entradas e 1 saída requer o teste de um total de 2 309 combinações de entradas. Visto que o número 2 309 é um número transcomputacional (ou seja, um número maior que 10 93 ), o problema de testar tal sistema de circuitos integrados é um problema transcomputacional. Isso significa que não há como verificar a exatidão do circuito para todas as combinações de entradas apenas por meio da força bruta .

Reconhecimento de padrões

Considere um q × q variedade do tabuleiro tipo, cada quadrado dos quais pode ter um dos k cores . Ao todo, existem k n padrões de cores , onde n = q 2 . O problema de determinar a melhor classificação dos padrões, de acordo com algum critério escolhido, pode ser resolvido por uma pesquisa em todos os padrões de cores possíveis. Para duas cores, essa pesquisa se torna transcomputacional quando a matriz é 18 × 18 ou maior. Para uma matriz 10 × 10, o problema se torna transcomputacional quando há 9 ou mais cores.

Isso tem alguma relevância nos estudos fisiológicos da retina . A retina contém cerca de um milhão de células sensíveis à luz . Mesmo que houvesse apenas dois estados possíveis para cada célula (digamos, um estado ativo e um estado inativo), o processamento da retina como um todo requer o processamento de mais de 10 300.000 bits de informação. Isso está muito além do limite de Bremermann .

Problemas gerais de sistemas

Um sistema de n variáveis, cada uma das quais podendo assumir k estados diferentes, pode ter k n estados de sistema possíveis. Para analisar tal sistema, um mínimo de k n bits de informação devem ser processados. O problema se torna transcomputacional quando k n > 10 93 . Isso acontece para os seguintes valores de k e n :

k 2 3 4 5 6 7 8 9 10
n 308 194 154 133 119 110 102 97 93

Implicações

A existência de problemas transcomputacionais do mundo real implica nas limitações dos computadores como ferramentas de processamento de dados. Este ponto é melhor resumido nas próprias palavras de Bremermann:

"As experiências de vários grupos que trabalham na solução de problemas, prova de teoremas e reconhecimento de padrões parecem apontar na mesma direção: Esses problemas são difíceis. Não parece haver uma estrada real ou um método simples que de uma só vez resolverá todos os nossos problemas. Minha discussão sobre as limitações finais na velocidade e na quantidade de processamento de dados pode ser resumida assim: Problemas envolvendo um vasto número de possibilidades não serão resolvidos pela simples quantidade de processamento de dados. Devemos buscar qualidade, refinamentos, truques , para cada engenhosidade em que podemos pensar. Computadores mais rápidos do que os de hoje serão uma grande ajuda. Vamos precisar deles. No entanto, quando estamos preocupados com problemas em princípio, os computadores atuais são tão rápidos quanto nunca serão .
Podemos esperar que a tecnologia de processamento de dados avance passo a passo - exatamente como a tecnologia comum tem feito. Há um desafio ilimitado para a engenhosidade aplicada a problemas específicos. Há também uma necessidade interminável de noções gerais e teorias para organizar a miríade de detalhes. "

Em ficção

Em O Guia do Mochileiro das Galáxias, de Douglas Adams , a Terra é um supercomputador, projetado para calcular a questão conhecida como "Questão Fundamental da Vida, O Universo e Tudo" (cuja resposta é conhecida como 42).

Veja também

Referências