Turing redutível em números naturais?

Question

Eu estou confuso sobre Turing redutível coisas.

Eu compreedido Turing redutível como este

"There is an oracle algorithm which is about set A and when this algorithm is derived from oracle algorithm of set B, it is called A is Turing-reducible to B"

Então por isso, eu tenho que resolver o problema.

N é o conjunto dos números naturais = {1, 2, 3, ...}

Permitir que Um ser o conjunto de todos os mesmo números naturais.

Deixe o B o conjunto de todos os números naturais ímpares.

Provar que A é Turing-redutível a B.

Aqui está o que eu tenho pensado.

O oracle algoritmo de A é n%2==0, o que n pertence aos números naturais.

E oracle algoritmo de B é n%2==1, o que n pertence aos números naturais.

Como posso derivar n%2==0 n%2==1 ?

Ou a minha abordagem é errado?

Obrigado por sua ajuda.

Answer 1

Para mostrar que $A$ é Turing-redutível a $B$ você precisa provar a existência de uma Máquina de Turing que é capaz de decidir $A$ quando lhes foi dado acesso a um oracle para $B$.

No seu caso específico de uma possível Máquina de Turing $M$ toma como entrada uma cadeia de caracteres $x \in \{0,1\}^*$ a codificação do número natural $n$ (Eu estou supondo que R $0 \in \mathbb{N}$) em binário e opera da seguinte forma:

• Ele vira o último bit de $x$.Agora $x$ representa um número ímpar iff o número de entrada $n$ foi mesmo.
• Ele invoca o oracle para $B$ com entrada $x$.
• Ele aceita iff, de acordo com a oracle, $x \in$B.

Observe que o fato de que $M$ tem acesso a um oracle para $B$ não significa que $M$ deve usar-se de que oracle.A seguir também é uma opção válida para $M$:

• Localize o último bit $y$ a seqüência de caracteres de entrada $x$.
• Se $y=0$ aceitar.Caso contrário, rejeitar.