Hipercomputação

Hipercomputação ou computação super-Turing refere-se aos modelos de computação que são mais poderosos que, ou são incomparáveis com, computabilidade de Turing. Isso inclui vários métodos hipotéticos para a Computação de Funções não-Turing computáveis, seguido por Algoritmo super-recursivas . O termo "computação super-Turing" surgiu em 1995 numa revista científica por Hava Siegelmann. O termo hipercomputação surgiu em 1999 por Jack Copeland and Diane Proudfoot. Esses termos não são exatamente sinônimos: computação super-Turing geralmente implica que o modelo proposto é supostamente fisicamente realizável, enquanto hipercomputação sofre com argumentos técnicos contra a sua realizabilidade física.

História

Um modelo mais poderoso que Máquinas de Turing foi introduzido por Alan Turing em seu artigo "Systems of logic based on ordinals" em 1939. Esse artigo investigou sistemas matemáticos em que dispunham de um oráculo, que podiam computar uma única e arbitrária (não-recursiva) função N -> N (naturais nos naturais). Ele usou esse dispositivo para provar que, mesmo nos sistemas mais poderosos, indecidibilidade ainda era presente. Essa máquina de Turing com oráculo foi apenas uma abstração matemática, não foi fisicamente realizada(construída).

Hipercomputação e a tese de Church-Turing

A Tese de Church-Turing diz que toda função que é algoritmicamente computável, pode ser computada em uma Máquina de Turing. Hipercomputadores computam funções que máquinas de Turing não podem, e assim, não computáveis pela tese de Church-Turing. Um exemplo de um problema que uma Máquina de Turing não pode resolver, é o Problema da Parada. Uma máquina de Turing não pode decidir se um programa arbitrário para, ou se executa para sempre. Algumas propostas de hipercomputadores podem simular um programa por um número infinito de passos, e pode dizer ao usuário se o programa parou ou não.

Propostas de Hipercomputadores

• Uma Máquina de Turing que pode completar infinitamente muitos passos. Simplesmente ser capaz de executar por um numero infinito de passos não é suficiente. Um modelo matemático é a "máquina Zeno" ou Zeno machine (inspirada no Paradoxos de Zeno). A Zeno machine realiza sua primeira computação em 1 minuto, a segunda computação em ½ minuto, a terceira em ¼ de minuto, etc. Então somando 1+½+¼+... (uma Progressão geométrica) pode-se ver que a máquina realiza infinitos passos num total de 2 minutos. Porém, algumas pessoas alegam que seguindo o raciocínio do Paradoxos de Zeno, a máquina Zeno não é só fisicamente impossível, ela é logicamente impossível também. Outro exemplo usa Dilatação do tempo para permitir a um computador gastar um tempo infinito realizando uma computação, enquanto que para um usuário, esse tempo seria finito)(iria necessitar uma quantidade infinita de energia para realizar a computação).
• A máquina de Turing com oráculo, definida por Turing em 1939.
• No meio da década de 1960, E Mark Gold e Hilary Putnam independentemente propuseram modelos de inferência indutiva ("funções recursivas limitantes" ou "limiting recursive functions" e "predicados de tentativa e erro" ou "trial and error predicate"], respectivamente). Esses modelos permitiram alguns conjuntos não-recursivos de números ou linguagens (inclusive todos os conjuntos recursivamente enumeráveis de linguagens) de serem "aprendidos no limite"; enquanto que, por definição, apenas conjuntos recursivos de números ou linguagens poderiam ser identificados por uma Máquina de Turing. Enquanto a máquina vai estabilizar para a resposta correta em qualquer conjunto que possa aprender(learnable set) num tempo finito, ela pode apenas identificar se é correto, apenas se for recursivo. Caso contrário, a corretude é estabelecida apenas se rodar a máquina eternamente, e nada que a máquina revisa, seria a resposta. Putnam identificou que essa nova interpretação como "a classe dos predicados empíricos", dizendo: "Se nós sempre supormos que a ultima resposta gerada é correta, nós iremos cometer um número finito de erros, mas nós iremos, uma hora, pegar a resposta correta (note, entretanto, que mesmo que peguemos a resposta correta (o fim da sequência finita), nós nunca teremos certeza que é a resposta correta)".[5] O artigo de L. K. Schubert em 1974 chamado de "Recursões limitantes iteradas e o problema da minimização de um programa"(iterated limiting recursion and the Program Minimization Problem) estudou o efeito de iterar um precedimento limitante; isso permite qualquer predicado aritmético de ser computado. Schubert escreveu: "Intuitivamente, identificação limitante iterada pode ser considerada com ode ordem superior da inferência indutiva realizada coletivamente por um conjunto que sempre cresce de máquinas de inferência indutiva de pequena ordem".
• Um Computador Real(Real Computer), que lida com máquinas hipotéticas de computar, que utilizam números reais de precisão infinita, podem realizar hipercomputação apenas se a física admitir variáveis reais (não apenas reais computáveis), e estes são "aproveitáveis" para computação. Isso pode necessitar de leis "bizarras" da física (por exemplo, uma constante física mensurável com um valor oracular, como a constante de Chaitin), e poderia no mínimo necessitar a habilidade de medir um valor real físico para precisão arbitrária apesar do Efeito Quantum e do barulho térmico(Thermal noise).
• Uma técnica proposta conhecida como "não-determinismo ilimitado"(unbounded nondeterminism) pode permitir a computação de funções não-computáveis. Há uma controvérsia na literatura sobre se essa técnica é coerente, e se ela realmente permite funções não-computáveis de serem computadas.
• Parece ser natural a a possibilidade de que viajar no tempo (a existência de curvas tipo tempo fechadas ou closed timelike curves (CTC)) torne a hipercomputação possível por si só. No entanto, isso não é verdade dado que um CTC(por si só) não consegue fornecer a quantidade ilimitada de armazenamento que uma computação infinita iria precisar. Ainda assim, existe espaço-tempo em que a região de CTC pode ser usada para hipercomputação relativística. O acesso a uma região de CTC pode permitir a rápida solução dos problemas PSPACE-completude, uma classe de complexidade que embora seja considerada Turing-decidível é considerada computacionalmente intratável.
• De acordo com o artigo de Hogarth, M. de 1992, um computador operando no espaço-tempo de Malament–Hogarth, ou orbitando ao redor de um buraco negro, poderia teoricamente computar funções não-Turing computáveis.
• em 1994, Hava Siegelmann provou que seu novo modelo computacional, a Artificial Recurrent Neural Network(Rede Neural Artificial Recorrente), poderia realizar hipercomputação(usando valor real com precisão infinita como peso para as sinapses). Esse modelo consiste em envolver uma Rede Neural Artificial em uma sucessão de estados discretos e finitos.
• a máquina de Turing de tempo infinito (infinite time Turing machine)é uma generalização da Máquina Zeno(Zeno Machine) que pode realizar computações infinitamente longas, cujos passos são enumerados por números ordinais potencialmente transfinitos. Isso modela uma máquina de Turing em uma outra forma, em que computações que não param(non-halting computation) são completas quando a máquina entra em um estado especial reservado para quando se chega a um número ordinal limite e em que os resultados da computação infinita precedente está disponível.
• Jan van Leeuwen e Jiří Wiedermann escreveram em 2000 um artigo que sugeria que a internet deveria ser modelada como um sistema computacional não uniforme equipado com uma função que recebe uma "advice String"(palavra de aviso) que representaria a habilidade dos computadores de serem melhorados(receberam upgrades).
• Uma sequência de símbolos é computável no limite(computable in the limit) se existir um programa finito, e que possivelmente não pare, em uma Máquina de Turing universal, que dê como saída cada símbolo da sequência. Isso inclui a a expansão diática de π e de todos os números reais computáveis(Computable Reals), mas ainda exclui todos os números reais não computáveis. Máquinas de Turing tradicionais não podem editar a saída anterior; máquinas de Turing generalizadas, como definiu Jürgen Schmidhuber, podem. Ele define construtivamente e descritivelmente a sequência de símbolos como aquelas que tem um programa finito, e que não pare(non-halting) rodando em uma máquina de Turing generalizada, tal que qualquer símbolo de saída eventualmente converge, isto é, ele não muda mais depois de um intervalo inicial de tempo finito. Devido a limitações primeiramente exibidas por Kurt Gödel, pode ser impossível prever o tempo de convergência em si por um programa que para (halting program), caso contrário, o Problema da parada poderia ser resolvido. Schmidhuber usa essa abordagem para definir o conjunto de, formalmente descritíveis, ou construtivamente computável, universos. Máquinas de Turing generalizadas podem resolver o problema da parada avaliando a sequência de Specker (Specker sequence).
• Um sistema mecânico-quântico, que de alguma forma usa sobreposição infinita de estados para computar uma função não-computável. Isso não é possível usando o modelo padrão de computador quântico de Bit quântico, porque é provado que um computador quântico regular é PSPACE-redutível(um computador quântico executando em tempo polinomial pode ser simulado por um computador clássico rodando em espaço polinomial).
• Em 1970, E.S. Santos definiu as classes baseadas em Lógica fuzzy, os "algoritmos fuzzy"(fuzzy algorithm) e as "máquinas de Turing fuzzy"(fuzzy Turing machines). Subsequentemente, L. Biacino and G. Gerla mostraram que essa definição permitiria a computação de linguagens não-recursivas; Eles definiram um conjunto alternativo de definições sem essas dificuldades. Jiří Wiedermann analisou a capacidade da proposta original de E.S Santos em 2004.
• Dmytro Taranovsky propôs um modelo finito dos tradicionais ramos de análise não-finitos, construído a partir de uma máquina de Turing equipada com uma função de crescimento rápido como seu oráculo. Por esse e outros modelos mais complicados, ele foi capaz de dar uma interpretação para aritmética de segunda ordem.

Análise da capacidade

Muitas propostas de hipercomputação procuram caminhos alternativos para ler um oráculo ou uma "advice String" embutida em uma máquina clássica. Outros permitem acesso para alguns níveis maiores da hierarquia aritmética. Por exemplo, a máquina de Turing supertask, sobre os pressupostos habituais, poderia ser capaz de computar qualquer predicado no grau da tabela verdade contendo $\Sigma _{1}^{0}$ ou $\Pi _{1}^{0}$. Recursão limitante, por contraste, pode computar qualquer predicado ou função no grau Turing correspondente, que é conhecido ser $\Delta _{2}^{0}$. Gold depois mostrou que recursão parcial limitante iria permitir a computação de precisamente $\Sigma _{2}^{0}$ predicados.

Modelo	predicados computáveis	Notas
supertasking	tt($\Sigma _{1}^{0},\Pi _{1}^{0}$)	dependente de um observador externo
limitante/tentativa-e-erro	$\Delta _{2}^{0}$
limitante iterado (k vezes)	$\Delta _{k+1}^{0}$
máquina de Blum-Shub-Smale		incomparável com tradicionais funções que computam número reais (computable reals)
espaço-tempo de Malament-Hogarth	hierarquia hiperaritmética	dependente da estrutura do espaço-tempo
Rede Neural Recorrente analógica	$\Delta _{1}^{0}[f]$	f é uma "advice function" que dá o peso das conexões; tamanho é limitado pelo tempo de execução
máquina de Turing de tempo infinito	$\geq T(\Sigma _{1}^{1})$
máquina de Turing clássica fuzzy	$\Sigma _{1}^{0}\cup \Pi _{1}^{0}$	Para qualquer t-norm computável.
oráculo de função crescente	$\Delta _{1}^{1}$	Para o modelo de uma sequência; $\Pi _{1}^{1}$ são r.e.

Taxonomia de metodologias computacionais super-recursivas

Burgin coletou uma lista do que ele chamou de algoritmos super-recursivos:

• Funções recursivas limitantes ("limiting recursive functions") e Funções parcialmente recursivas limitantes ("limiting partial recursive functions") (E.M. Gold)
• Predicados de tentativa e erro ("trial and error predicates") (Hilary Putnam)
• Máquinas de inferência indutiva ("inductive inference machines") (Carl Smith)
• Máquinas de Turing indutivas ("inductive Turing machines"), que realizam cálculos parecidos com os de uma Máquina de Turing e produzem resultado após um numero finito de passos. (Mark Burgin)
• Limite de máquina de Turing ("limit Turing machines"), que realizam cálculos similares aos de uma Máquina de Turing, mas seu resultado final são limites de seu resultado imediato. (Mark Burgin)
• Máquinas de tentativa e erro ("trial-and-error machines"). (Ja. Hintikka and A. Mutanen)
• Máquinas de Turing genéricas ("general Turing machines"). (J. Schmidhuber)
• Máquinas de Internet ("internet machines"). (van Leeuwen, J. and Wiedermann, J.)
• Computadores evolutivos ("evolutionary computers"), que usam DNA como valor para uma função. (Darko Roglic)
• Computação fuzzy ("fuzzy computation"). (Jirí Wiedermann)
• Máquinas de Turing evolutivas ("evolutionary Turing machines"). (Eugene Eberbach)

No mesmo livro, ele também apresentou uma lista de esquemas de algoritmos(algorithmic schemes):

• Máquinas de Turing com oráculos arbitrários ("Turing machines with arbitrary oracles") (Alan Turing)
• Operadores transrecursivos ("transrecursives operators") (Borodyanskii and Burgin)
• Máquinas que computam com números reais ("machines that compute with real numbers") (L. Blum, F. Cucker, M. Shub, and S. Smale)
• Rede neural baseada em números reais ("neural network based on real numbers") (Hava Siegelmann)

Crítica

Martin Davis, em suas escritas sobre hipercomputação, refere-se a esse assunto como "um mito" e oferece contra-argumentos sobre a capacidade de realização física de hipercomputadores. Para sua teoria, ele argumenta contra as alegações de que isso é um novo campo fundado na década de 1990. Esse ponto de vista baseia-se na história da teoria da computabilidade (graus de insolubilidade, computabilidade das funções, números reais e ordinais), como já mencionado acima.

Andrew Hodges escreveu um comentário crítico no artigo de Copeland e Proudfoot.