Redução de Turing

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

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 domínio 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

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

Exemplos

Deixando $W_{e}$ denotar o conjunto de valores de entrada para o qual a máquina de Turing com índices e para. 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 para em todas as entrada ou não para 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

• 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 sequê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

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^{(\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

• 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