# 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.