Turing réductible en nombres naturels ?

Question

Je suis confus au sujet des choses réductibles de Turing.

J'ai compris Turing réductible comme ça

"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"

Donc par là, je dois résoudre le problème.

N est l'ensemble des nombres naturels = {1, 2, 3, ...}

Soit A l’ensemble de tous les nombres naturels pairs.

Soit B l’ensemble de tous les nombres naturels impairs.

Montrer que A est Turing-réductible à B.

Voici ce que j'ai pensé.

L'algorithme oracle de A est n%2==0 dont n appartient aux nombres naturels.

Et l'algorithme oracle de B est n%2==1 dont n appartient aux nombres naturels.

Comment puis-je dériver n%2==0 de n%2==1 ?

Ou mon approche est fausse ?

Merci pour votre aide.

Answer 1

Montrer que $A$ Turing est-il réductible à $B$ vous devez prouver l'existence d'une machine de Turing capable de décider $A$ lorsqu'on lui donne accès à un oracle pour $B$.

Dans votre cas spécifique, une possible machine de Turing M$ prend en entrée une chaîne $x \in \{0,1\}^*$ coder l'entier naturel $n$ (Je suppose $0 \in \mathbb{N}$) en binaire et fonctionne comme suit :

• Il retourne le dernier morceau de $x$.Maintenant $x$ représente un nombre impair si le nombre saisi $n$ était égal.
• Il invoque l'oracle pour $B$ avec entrée $x$.
• Il accepte si, selon l'oracle, $x \en B$.

Notez que le fait que M$ a accès à un oracle pour $B$ ne veut pas dire que M$ Je dois utiliser cet oracle.Ce qui suit est également un choix valable pour M$:

• Localisez le dernier morceau $y$ de la chaîne d'entrée $x$.
• Si $y=0$ accepter.Sinon, rejetez.