Redução de Turing

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde abril de 2013)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.

Na Teoria da Computação, a redução de Turing de um problema A para um problema B, nomeado após Alan Turing, é uma redução que resolve A, assumindo que B já é conhecido(Rogers 1967, Soare 1987). Esta pode ser entendida como um algoritmo que pode ser usado para resolver A se este for for válido como uma sub-rotina que resolve B. De uma maneira mais formal, a redução de Turing é uma função computável por uma máquina Turing com um oráculo para B. A redução de turing pode ser aplicada tanto para problemas de decisão quanto para problemas problemas de função.

Se uma redução de Turing de A para B existe, então todo algoritmo que resolve B pode ser usado para produzir um algoritmo que resolve A, inserindo o algoritmo que resolve B em cada lugar onde a máquina de Turing com um oráculo, ao computar A, consulta o oráculo de B. Entretanto, já que a máquina Turing com oráculo pode fazer um grande número de consultas ao oráculo, o algoritmo resultante pode requerer mais tempo do que o normal do que qualquer M ou máquina Turing com oráculo e pode necessitar de tanto espaço quanto os dois juntos.

A primeira definição formal de uma computação relativa, depois chamada de redutibilidade relativa, foi dada por Alan Turing em 1939 na definição da máquina de Turing com oráculo. Depois, em 1943 e 1952, Stephen Kleene definiu um conceito equivalente sobre a definição de funções recursivas. Em 1944 Emil Post usou a definição de "Redução de Turing" para se referir ao conceito.

Definição[editar | editar código-fonte]

Dados dois conjuntos A,B \subseteq \mathbb{N} de números naturais, dizemos que A é turing redutível para B e escrevemos

A \leq_T B

Se existe uma máquina de Turing com oráculo que computa uma função indicadora de A quando executa com o oráculo B. Nesse caso, também podemos dizer que A é B-recursiva e B-computável.

Se existe uma máquina de Turing com oráculo que, quando roda com o oráculo B, computa uma função parcial com o dominio A, então A é Turing recursível e turing computável.

Dizemos que A é Turing equivalente de B e escrevemos A \equiv_T B\, Se os dois A \leq_T B e B \leq_T A.As classes equivalentes de conjuntos de "Turing Equivalente" são chamados de graus de Turing. O grau de Turing de um conjunto X é descrito por \textbf{deg}(X).

Dado um conjunto \mathcal{X} \subseteq \mathcal{P}(\mathbb{N}), um conjunto A \subseteq \mathbb{N} é chamado de "Turing-difícil" para \mathcal{X} se X \leq_T A para todo X \in \mathcal{X}. Se adicionalmente A \in \mathcal{X} e A é chamado Turing completo para \mathcal{X}.

Relação de completude de Turing à universalidade computacional[editar | editar código-fonte]

Turing completude, como já foi definido acima, corresponde apenas parcialmente a Turing completude no sentido dado na computação universal. Especificamente, uma máquina de Turing é uma máquina de Turing universal sse o problema da parada(i.e., o conjunto de entrada para cada eventual parada) é uma redução muitas para uma. Assim, uma condição necessária, mas insuficiente para uma máquina ser computacionalmente universal, é que problema da parada seja Turing-completa para o conjunto \mathcal{X} de conjuntos recursivamente enumeráveis​​.

Exemplos[editar | editar código-fonte]

Deixando W_e denotar o conjunto de valores de entrada para o qual a máquina de Turing com índices e pára. Depois os conjuntos A = \{e \mid e \in W_e\} e B = \{(e,n) \mid n \in W_e \} são Turing equivalente (aqui (e,n) denota uma função de emparelhamento eficaz). A redução mostrada A \leq_T B pode ser construída usando o fato de e \in A \Leftrightarrow (e,e) \in B. Dado um par (e,n), um novo índice i(e,n) pode ser construído usando o teorema Smn de tal forma que o programa codificado por i(e,n) ignora sua entrada e apenas simula o cálculo da máquina com o índice e da entrada n.Em particular, a máquina com o índice i(e,n) ou pára em todas as entrada ou não pára em nenhuma entrada. Assim, i(e,n) \in A \Leftrightarrow (e,n) \in B válidos para todos os e e n. Porque a função i é computável, isso mostra B \leq_T A. As reduções apresentadas aqui não são apenas reduções de Turing, mas reduções de muitos para um, discutidos abaixo.

Propriedades[editar | editar código-fonte]

  • Cada conjunto é Turing equivalente ao seu complemento
  • Cada conjunto computável é Turing redutível a qualquer outro conjunto computável. Porque esses conjuntos podem ser computados sem oráculo, eles podem ser computado por uma máquina de Turing com oráculo que ignora o oráculo que foi dado
  • A relação \leq_T é transitiva: se A \leq_T B e B \leq_T C então A \leq_T C. Além disso, A \leq A vale para cada conjunto A e assim a relação \leq_T é pré-ordenada (isso não é uma ordenação parcial, porque A \leq_T B e B \leq_T A não implicam necessariamente em A = B).
  • Existem pares de conjuntos (A,B) tal como A não é turing redutível a B e B não é turing redutível a A. Assim \leq_T não é uma ordem linear.
  • Existem infinitas seqüências decrescentes de conjuntos sobre \leq_T. Essa relação não é bem fundamentada (well-founded).
  • Cada conjunto é Turing redutível à seu própria salto Turing, mas o salto Turing de um conjunto nunca é Turing redutível ao conjunto original

O uso da redução[editar | editar código-fonte]

Uma vez que cada redução de um conjunto B para um conjunto A tem que determinar se um único elemento está em A em um número de passos finitos, só se pode fazer um número finito de consultas aos membros do conjunto B. Quando a quantidade de informações sobre o conjunto B, usada para computar um único bit de A é detalhada, ela é feita precisamente pela função de uso. Formalmente, o uso de uma redução é a função que envia um número natural n para o maior número natural m cuja participação está no conjunto B e foi consultada pela redução, enquanto determinada a participação de n em A.

Reduções fortes[editar | editar código-fonte]

Existem duas maneiras comuns de produzir reduções mais fortes do que redutibilidade de Turing. A primeira maneira é limitar o número e a maneira das consultas ao oráculo.

  • Um conjunto A é "redutível de muitos para um" para B se há uma função totalmente computável f tal que um elemento n está em A se e somente se f(n) está em B. Esta função pode ser usada para gerar uma redução de Turing (computando f(n), consultando o oráculo e interpretando o resultado).
  • Uma redução por tabela verdade ou uma redução por tabela verdade fraca deve apresentar, ao mesmo tempo, todas as suas consultas ao oráculo. Numa redução por tabela verdade, a redução também dá uma função booleana (uma tabela verdade) que, quando dado as respostas às consultas, irá produzir a resposta final da redução. Em uma redução por tabela verdade fraca, a redução usa as respostas do oráculo como base para aproximar a computação, dependendo das respostas dadas (mas não usando o oráculo). Equivalentemente, uma redução tabela verdade fraca é aquela para o qual o uso da redução é limitada por uma função computável. Por esta razão, as reduções tabela verdade fraca às vezes são chamadas de reduções "limitada Turing".

A segunda maneira de produzir uma noção mais forte de redutibilidade é limitar os recursos computacionais que o programa de implementação da redução de Turing pode usar. Esses limites da redução na Complexidade computacional são importantes quando estudamos classes subrecursivas, tais como complexidade polinomial. Um conjunto A é redutível em tempo polinomial para o conjunto B se existir uma redução de turing de A para B que rode em tempo polinomial. O conceito de redução log-space é parecido.

Observe que, embora essas reduções são mais fortes no sentido de que eles fornecem uma distinção mais fina em classes de equivalência, e têm exigências mais restritivas do que as reduções de Turing, isso é porque as reduções são menos poderosas; não pode haver nenhuma forma de construir uma redução "muitos para um" de um conjunto para outro, mesmo quando uma redução de Turing existe para os mesmos conjuntos.

Reduções fracas[editar | editar código-fonte]

De acordo com a Tese de Church-Turing, uma redução de turing é a forma mais geral de uma redução efetivamente calculável. No entanto, as reduções mais fracas também são consideradas. Um conjunto A é dito como aritmético em B se A é definível pela fórmula aritmética de Peano sendo B como um parâmetro. O conjunto A é hiper aritmético em B se existe um ordinal recursivo α tal como A é computável de B^{(\alpha)}, o α-iterado salto Turing de B. A noção de universo construtível é um importante noção de retutibilidade na teoria dos conjuntos.

Referências[editar | editar código-fonte]

  • M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9.
  • S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland.
  • S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics v. 2 n. 59, 379—407.
  • E. Post, 1944. "Recursively enumerable sets of positive integers and their decision problems." Bulletin of the American Mathematical Society, v. 50, pp. 284-316. Reprinted in "The Undecidable", M. Davis ed., 1965.
  • A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.
  • H. Rogers, 1967. Theory of recursive functions and effective computability. McGraw-Hill.
  • R. Soare, 1987. Recursively enumerable sets and degrees, Springer.
  • Davis, Martin (November 2006). "What is...Turing Reducibility?" (PDF). Notices of the American Mathematical Society 53 (10): pp.1218–1219 pp..

Ligações externas[editar | editar código-fonte]