Btukfyl

Este artigo ou secção contém fontes no fim do texto, mas que não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (desde abril de 2013) Por favor, melhore este artigo inserindo fontes 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 |

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

A≤TB{displaystyle Aleq _{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{displaystyle A} é Turing equivalente de B{displaystyle B} e escrevemos A≡TB{displaystyle Aequiv _{T}B,} Se os dois A≤TB{displaystyle Aleq _{T}B} e B≤TA.{displaystyle Bleq _{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{displaystyle X} é descrito por deg(X){displaystyle {textbf {deg}}(X)}.

Dado um conjunto X⊆P(N){displaystyle {mathcal {X}}subseteq {mathcal {P}}(mathbb {N} )}, um conjunto A⊆N{displaystyle Asubseteq mathbb {N} } é chamado de "Turing-difícil" para X{displaystyle {mathcal {X}}} se X≤TA{displaystyle Xleq _{T}A} para todo X∈X{displaystyle Xin {mathcal {X}}}. Se adicionalmente A∈X{displaystyle Ain {mathcal {X}}} e A{displaystyle A} é chamado Turing completo para X{displaystyle {mathcal {X}}}.

Relação de completude de Turing à universalidade computacional |

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 X{displaystyle {mathcal {X}}} de conjuntos recursivamente enumeráveis​​.

Exemplos |

Deixando We{displaystyle 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∣e∈We}{displaystyle A={emid ein W_{e}}} e B={(e,n)∣n∈We}{displaystyle B={(e,n)mid nin W_{e}}} são Turing equivalente (aqui (e,n){displaystyle (e,n)} denota uma função de emparelhamento eficaz). A redução mostrada A≤TB{displaystyle Aleq _{T}B} pode ser construída usando o fato de e∈A⇔(e,e)∈B{displaystyle ein ALeftrightarrow (e,e)in B}. Dado um par (e,n){displaystyle (e,n)}, um novo índice i(e,n){displaystyle i(e,n)} pode ser construído usando o teorema Smn de tal forma que o programa codificado por i(e,n){displaystyle 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){displaystyle i(e,n)} ou pára em todas as entrada ou não pára em nenhuma entrada. Assim, i(e,n)∈A⇔(e,n)∈B{displaystyle i(e,n)in ALeftrightarrow (e,n)in B} válidos para todos os e e n. Porque a função i é computável, isso mostra B≤TA{displaystyle Bleq _{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 |

• 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 ≤T{displaystyle leq _{T}} é transitiva: se A≤TB{displaystyle Aleq _{T}B} e B≤TC{displaystyle Bleq _{T}C} então A≤TC{displaystyle Aleq _{T}C}. Além disso, A≤A{displaystyle Aleq A} vale para cada conjunto A e assim a relação ≤T{displaystyle leq _{T}} é pré-ordenada (isso não é uma ordenação parcial, porque A≤TB{displaystyle Aleq _{T}B} e B≤TA{displaystyle Bleq _{T}A} não implicam necessariamente em A=B{displaystyle A=B}).


• Existem pares de conjuntos (A,B){displaystyle (A,B)} tal como A não é turing redutível a B e B não é turing redutível a A. Assim ≤T{displaystyle leq _{T}} não é uma ordem linear.


• Existem infinitas seqüências decrescentes de conjuntos sobre ≤T{displaystyle 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 |

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 |

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 |

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(α){displaystyle 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 |

• 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 (2006). «What is...Turing Reducibility?» (PDF). Notices of the American Mathematical Society. 53 (10): 1218–1219. Consultado em 16 de janeiro de 2008 
  

Ligações externas |

• NIST Dictionary of Algorithms and Data Structures: Turing reduction