Problema transcomputacional

Na teórica complexidade computacional, um problema transcomputacional é um problema que exige processamento de mais que 10⁹³ bits de informação. Qualquer numero maior que 10⁹³ é chamado de numero transcomputacional. O numero 10⁹³, chamado limite de Bremermann's, é, de acordo com Hans-Joachim Bremermann, o total de números de bits processado por um computador hipotético do tamanho da Terra dentro dentro de um período de tempo igual a idade estimada da Terra. O termo transcomputacional foi cunhado por Bremermann.

Exemplos de problemas transcomputacional

Problema do caixeiro viajante

O problema do caixeiro viajante é o problema de encontrar um circuito que possua a menor distância, começando numa qualquer cidade, dentro de uma lista de cidades, visitando cada cidade precisamente uma vez e regressando à cidade inicial. Se houver n cidades na lista, o numero de possibilidades do circuito é n! tendo em vista que 66! é aproximadamente igual a 5,443449391 * 10⁹² e 67! de 3,647111092 * 10⁹⁴, o problema de enumerar todos os passeios possíveis torna-se transcomputational para n> 66.

Teste de circuitos integrados

Exaustivamente testar todas as combinações de um circuito integrado com 308 entradas e uma saída requer testes de um total de 2³⁰⁸ combinações de entradas. Umas vez que o numero 2³⁰⁸ é um numero transcomputacional (isto é, um numero maior que 10³⁰⁸), o problema de testar tal sistema de circuitos integrados se transforma em um problema transcomputacional . Isto significa que não existe uma maneira que possa verificar o corretude do circuito para todas as combinações de entradas através da força bruta sozinho.

Reconhecimento de Padrões

Considere uma matriz q ×q do tabuleiro de xadrez onde cada quadrado pode ter uma das k cores. Ao todo são kⁿ padrões de cores, onde n=q². O problema de determinar a melhor classificação de padrões, de acordo com algum critério escolhido, pode ser resolvido por uma busca através de todos os padrões de cores possíveis. Para duas cores, esta busca se torna transcomputacional quando a matriz é 18x18 ou maior. Para uma matriz 10x10, o problema torna-se transcomputacional quanto ha 9 ou mais cores.

Isso tem alguma relevância em estudos fisiológicos da retina. A retina contem cerca um milhão de células sensíveis a luz. Mesmo se houver apenas 2 estados possíveis para cada célula (tal como um estado ativo e um estado inativo) o processamento da retina como um todo exige o processamento de mais de 10^300,000 bits de informação. Isto é muito mais alem do o limite de Bremermann's.

Problemas gerais do sistema

Um sistema de n variáveis, cada uma deles pode pegar k estados diferentes, pode ter kⁿ estados possíveis do sistema. Para analisar um sistema assim, um mínimo de kⁿ bits de informação tem que ser processados. O problema torna-se transcomputacional quando kⁿ > 10⁹³. 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 do mundo real transcomputacional implica na limitação dos computadores como ferramentas de processamento de dados. Este ponto é melhor sintetizado nas palavras do próprio Bremermann:

"As experiências de vários grupos que trabalham na resolução de problemas, provar de teoremas e reconhecer padrões, todos parecem apontar para uma mesma direcao: Estes problemas são difíceis. Não parece haver uma estrada real ou um simples método que de um só golpe vai resolver todos os nossos problemas. Minha discussão das limitações finais sobre a velocidade e a quantidade de processamento de dados pode ser resumida assim: Os problemas envolvendo um grande numero de possibilidades não serão resolvidos pela grande quantidade de processamento de dados. Devemos olhar para qualidade, para refinamentos, para truques, para cada elementos que podemos pensar. Computadores mais rápidos do que os de hoje serão uma ótima ajuda. Nós vamos precisar deles. No entanto, quando nós estamos preocupados com problema em sua essencia, os computadores atuais são quase tão rápidos como sempre serao.

Nós podemos esperar que a tecnologia de processamento de dados irá avançar passo a passo - assim como a tecnologia comum fez. Há um desafio ilimitado para engenhosidades aplicada para problemas específicos. Há também uma necessidade infinita por noções gerais e teorias para organizar a infinidade de detalhes."

Na ficção

Em Douglas Adams é O Guia do Mochileiro das Galáxias , a Terra é um supercomputador, projetado para calcular a "Questão Fundamental da Vida, O Universo e Tudo".