Redução de Turing – Wikipédia, a enciclopédia livre

Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. Ajude a melhorar este artigo inserindo citações no corpo do artigo. (Abril de 2013)

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. Esta pode ser entendida como um algoritmo que pode ser usado para resolver A se este 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 ${\displaystyle A,B\subseteq \mathbb {N} }$ de números naturais, dizemos que ${\displaystyle A}$ é Turing redutível para ${\displaystyle B}$ e escrevemos

${\displaystyle 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 domínio A, então A é Turing recursível e Turing computável.

Dizemos que ${\displaystyle A}$ é Turing equivalente de ${\displaystyle B}$ e escrevemos ${\displaystyle A\equiv _{T}B\,}$ Se os dois ${\displaystyle A\leq _{T}B}$ e ${\displaystyle 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 ${\displaystyle X}$ é descrito por ${\displaystyle {\textbf {deg}}(X)}$.

Dado um conjunto ${\displaystyle {\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )}$, um conjunto ${\displaystyle A\subseteq \mathbb {N} }$ é chamado de "Turing-difícil" para ${\displaystyle {\mathcal {X}}}$ se ${\displaystyle X\leq _{T}A}$ para todo ${\displaystyle X\in {\mathcal {X}}}$. Se adicionalmente ${\displaystyle A\in {\mathcal {X}}}$ e ${\displaystyle A}$ é chamado Turing completo para ${\displaystyle {\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 se 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 ${\displaystyle {\mathcal {X}}}$ de conjuntos recursivamente enumeráveis.

Exemplos[editar | editar código-fonte]

Deixando ${\displaystyle W_{e}}$ denotar o conjunto de valores de entrada para o qual a máquina de Turing com índices e para. Depois os conjuntos ${\displaystyle A=\{e\mid e\in W_{e}\}}$ e ${\displaystyle B=\{(e,n)\mid n\in W_{e}\}}$ são Turing equivalente (aqui ${\displaystyle (e,n)}$ denota uma função de emparelhamento eficaz). A redução mostrada ${\displaystyle A\leq _{T}B}$ pode ser construída usando o fato de ${\displaystyle e\in A\Leftrightarrow (e,e)\in B}$. Dado um par ${\displaystyle (e,n)}$, um novo índice ${\displaystyle i(e,n)}$ pode ser construído usando o Teorema Smn de tal forma que o programa codificado por ${\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 ${\displaystyle i(e,n)}$ ou para em todas as entrada ou não para em nenhuma entrada. Assim, ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \leq _{T}}$ é transitiva: se ${\displaystyle A\leq _{T}B}$ e ${\displaystyle B\leq _{T}C}$ então ${\displaystyle A\leq _{T}C}$. Além disso, ${\displaystyle A\leq A}$ vale para cada conjunto A e assim a relação ${\displaystyle \leq _{T}}$ é pré-ordenada (isso não é uma ordenação parcial, porque ${\displaystyle A\leq _{T}B}$ e ${\displaystyle B\leq _{T}A}$ não implicam necessariamente em ${\displaystyle A=B}$).
• Existem pares de conjuntos ${\displaystyle (A,B)}$ tal como A não é Turing redutível a B e B não é Turing redutível a A. Assim ${\displaystyle \leq _{T}}$ não é uma ordem linear.
• Existem infinitas sequências decrescentes de conjuntos sobre ${\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[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 ${\displaystyle B^{(\alpha )}}$, o α-iterado salto Turing de B. A noção de universo construtível é um importante noção de redutibilidade 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 (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[editar | editar código-fonte]

• NIST Dictionary of Algorithms and Data Structures: Turing reduction