Máquina oráculo

Em teoria da computação, uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão. Ela pode ser vista como uma máquina de Turing com uma caixa preta, chamada de oráculo, que é capaz de decidir alguns problemas de decisão em uma única operação. O problema pode ser de qualquer classe de complexidade. Até mesmo problemas indecidíveis, como o problema da parada, podem ser decididos nela.

Definição

Uma máquina oráculo é uma máquina de Turing conectada a um oráculo. O oráculo, neste contexto, é visto como uma entidade capaz de responder a uma coleção de perguntas, e é geralmente representado como um subconjunto A dos números naturais. Fica claro então que a máquina oráculo pode executar todas as operações usuais de uma máquina de Turing, e pode também fazer consultas ao oráculo na procura de uma resposta a uma pergunta, da forma "x está em A?", específica.

A definição dada aqui é uma das várias definições possíveis para uma máquina oráculo. Todas essas definições são equivalentes, já que definem, de forma comum, quais funções f específicas podem ser computadas por uma máquina oráculo com um oráculo A.

Uma máquina oráculo, assim como uma máquina de Turing, possui:

• uma fita: uma sequencia infinita de células (sem começo nem fim), em que cada célula pode conter um B (branco) ou um 1;
• uma cabeça de leitura/escrita, que se posiciona sobre uma célula da fita e pode ler seu conteúdo, escrever um novo conteúdo, e mover-se para direita ou para esquerda ao longo da fita;
• um mecanismo de controle, que pode estar em um de um número finito de estados, e que executará diferentes ações (ler um dado, escrever um dado, mover a cabeça de leitura/escrita, e mudar seu estado) dependendo do seu estado atual e do dado lido da fita.

Além desses componentes, uma máquina oráculo também possui:

• uma fita do oráculo, na qual uma sequência infinita de B's e 1's são impressas, correspondendo à função característica do subconjunto oráculo A;
• uma cabeça do oráculo, que (assim como a cabeça de leitura/escrita) pode se mover para a esquerda ou para a direita ao longo da fita do oráculo lendo seus dados, mas não efetua escritas.

Definição formal

Uma máquina oráculo é uma 4-upla $M=\langle Q,\delta ,q_{0},F\rangle$ onde:

• $Q$ é um conjunto finito de estados;
• $\delta :Q\times \{B,1\}^{2}\rightarrow Q\times \{B,1\}\times \{L,R\}^{2}$ é uma função parcial chamada função transição, onde L é um movimento para esquerda e R é um movimento para a direita;
• $q_{0}\in Q$ é o estado inicial;
• $F\subseteq Q$ é o conjunto de estados de parada.

Uma máquina oráculo é inicializada com a fita contendo uma entrada de um número finito de 1's e o restante em branco, a fita do oráculo é inicializada com a função característica do oráculo, A, e a máquina de Turing no estado q₀ com a cabeça de leitura/escrita sobre a primeira célula preenchida (sem estar em branco) da fita, e a cabeça do oráculo sobre a célula da fita do oráculo que corresponde a $\chi _{A}(0)$. A partir dai, ela opera de acordo com $\delta$: se a máquina de Turing es´ta sobre um estado q, a cabeça de leitura/escrita está lendo um símbolo S₁, e a cabeça do oráculo está lendo S₂, então se $\delta (q,S_{1},S_{2})=(q',S_{1}',D_{1},D_{2})$, a máquina entra no estado $q'$, a cabeça de escrita/leitura escreve o símbolo S₁' no lugar de S₁, e então se move uma célula na direção D₁ e a cabeça do oráculo se move uma célula na direção D₂. Neste ponto se $q'$ é um estado de parada, a máquina para, se não repete o procedimento novamente.

Máquinas de turing computam funções da seguinte maneira: seja f uma função dos naturais para os naturais, MA é uma máquina de Turing com um oráculo A, e sempre que MA é inicializada com uma fita consistindo de n+1 1's consecutivos (e branco nas outras células) MA eventualmente para com f(n) 1's na fita, então é dito que MA computa a função f. Uma definição similar pode ser feita para funções com mais de uma variável, ou funções parciais.

Se existe um máquina oráculo M que computa uma função f com um oráculo A, f é dita ser A-computável. Se f é a função característica de um conjunto B, B também é dita ser A-computável, e M é dita ser uma redução de Turing de B para A.

Classe de complexidade das máquinas oráculo

A classe de complexidade de problemas de decisão solúveis por um algoritmo na classe A com um oráculo para a linguagem L é chamado A^L. Por exemplo, P^SAT é a classe de problemas solúveis em tempo polinomial por uma máquina de Turing determinística com um oráculo parao o problema da satisfatibilidade. A notação A^B pode ser estendida para um conjunto de linguagens B (ou uma classe de complexidade B), usando a seguinte definição:

$A^{B}=\bigcup _{L\in B}A^{L}$

Quando uma linguagem L é completa para uma classe B, então A^L=A^B dado que máquinas em A podem executar reduções usadas na definição de completude da classe B. Em particular, já que SAT é NP-Completo com respeito a reduções em tempo polinomial, P^SAT=P^NP. Entretanto, se A = DLOGTIME, então A^SAT pode não ser igual a A^NP.

É óbvio que NP ⊆ P^NP, mas a questão de se NP^NP, P^NP, NP, e P são iguais ainda não é bem definida. Acredita-se que elas são diferentes, e isso leva à definição da hierarquia polinomial.

Máquinas oráculo são muito úteis na investigação da relação entre a complexidade das classe P e NP, considerando a relação P^A e NP^A para um oráculo A. Em particular, foi mostrado que existe linguagens A e B tais que P^A=NP^A e P^B≠NP^B.

É interessante considerar o caso onde um oráculo é escolhido aleatóriamente entre todos os possíveis oráculos (um conjunto infinito). Foi mostrado que nesse caso, com probabilidade 1, P^A≠NP^A. Quando a questão é verdadeira para quase todos os oráculos, é dito que é verdadeira para um oráculo aleatório. Esta escolha de terminologia é justificada pelo fato que oráculos aleatórios dão suporte a uma afirmação com probabilidade de 0 ou 1, apenas. Isso é tido como evidência que P≠NP. Uma afirmação pode ser verdadeira para um oráculo aleatório e falsa para uma máquina de Turing comum, ao mesmo tempo.

Oráculos e problemas de parada

É possível propor a existência de um oráculo que computa uma função não-computável, como a resposta ao problema da parada ou problemas equivalentes a ele. Uma máquina com um oráculo desse tipo é um hipercomputador.

Curiosamente, o paradoxo da parada ainda se aplica a essas máquinas; embora elas determinem se máquinas de Turing param ou não para certas entradas, elas não conseguem determinar, em geral, se máquinas equivalentes a elas irão parar. Esse fato cria uma hierarquia de máquinas, chama de hierarquia aritmética, cada uma com oráculos mais poderosos e até mesmo problemas da parada mais difíceis.

Mais leituras

• Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
• C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Section 14.3: Oracles, pp. 339–343.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997. ISBN 0-534-94728-X. Section 9.2: Relativization, pp.318–321.
• Martin Davis, editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965.