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.
Índice
1 Definição
1.1 Definição formal
2 Classe de complexidade das máquinas oráculo
3 Oráculos e problemas de parada
4 Referências
5 Mais leituras
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=⟨Q,δ,q0,F⟩{displaystyle M=langle Q,delta ,q_{0},Frangle }
Q{displaystyle Q}é um conjunto finito de estados;
δ:Q×{B,1}2→Q×{B,1}×{L,R}2{displaystyle delta :Qtimes {B,1}^{2}rightarrow Qtimes {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;
q0∈Q{displaystyle q_{0}in Q}é o estado inicial;
F⊆Q{displaystyle Fsubseteq 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 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(0){displaystyle chi _{A}(0)}
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 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:
- AB=⋃L∈BAL{displaystyle A^{B}=bigcup _{Lin B}A^{L}}
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
↑ T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)
↑ C. H. Bennett, J. Gill. Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1. SIAM Journal on Computing, 10(1): 96-113 (1981)
↑ Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, Pankaj Rohatgi. The Random Oracle Hypothesis is False. Journal of Computer and System Sciences, volume 49, issue 1, pp.24–39. August 1994. ISSN 0022-0000. http://citeseer.ist.psu.edu/282397.html
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.
