Máquina oráculoEm 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çãoUma 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:
Além desses componentes, uma máquina oráculo também possui:
Definição formalUma máquina oráculo é uma 4-upla onde:
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 q0 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 . A partir dai, ela opera de acordo com : se a máquina de Turing es´ta sobre um estado q, a cabeça de leitura/escrita está lendo um símbolo S1, e a cabeça do oráculo está lendo S2, então se , a máquina entra no estado , a cabeça de escrita/leitura escreve o símbolo S1' no lugar de S1, e então se move uma célula na direção D1 e a cabeça do oráculo se move uma célula na direção D2. Neste ponto se é 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áculoA 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 AL. Por exemplo, PSAT é 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 AB pode ser estendida para um conjunto de linguagens B (ou uma classe de complexidade B), usando a seguinte definição: Quando uma linguagem L é completa para uma classe B, então AL=AB 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, PSAT=PNP. Entretanto, se A = DLOGTIME, então ASAT pode não ser igual a ANP. É óbvio que NP ⊆ PNP, mas a questão de se NPNP, PNP, 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 PA e NPA para um oráculo A. Em particular, foi mostrado que existe linguagens A e B tais que PA=NPA e PB≠NPB.[1] É 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, PA≠NPA.[2] 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.[3] 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. Referências
Mais leituras
|