# 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$_0$ 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$_1$, e a cabeça do oráculo está lendo S$_2$, 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$_1$' no lugar de S$_1$, e então se move uma célula na direção D$_1$ e a cabeça do oráculo se move uma célula na direção D$_2$. 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.