In natürlichen Zahlen reduzierbar?

Question

Ich bin verwirrt, um reduzierbare Dinge zu turnen.

Ich habe verstanden, dass das Turing reduzierbar ist wie dieses

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

Also muss ich das Problem lösen.

n ist der Satz natürlicher Zahlen= {1, 2, 3, ...}

lass ein Set aller selbst natürlichen Zahlen sein.

s s sei der Satz aller ungeraden natürlichen Nummern.

beweisen, dass ein Turning-reduzierbar auf b ist.

hier ist das, was ich gedacht habe.

Der Oracle-Algorithmus von A ist n% 2== 0, der n auf natürliche Zahlen gehört.

und Oracle-Algorithmus von B ist n% 2== 1, der n zu natürlichen Zahlen gehört.

Wie kann ich n% 2== 0 von n% 2== 1?

oder mein Ansatz ist falsch?

Danke für Ihre Hilfe.

Answer 1

Um anzuzeigen, dass $ A $ Turing-Reduktible auf $ B $ Sie benötigen, um das zu beweisen Existenz einer Turing-Maschine, die in der Lage ist, $ A $ zu entscheiden, wenn der Zugriff auf ein Oracle für $ B $ .

in Ihrem speziellen Fall Eine mögliche Turing-Maschine $ M $ dauert, wie ein Eingang eine Zeichenfolge $ x \ in \ {0 , 1 \} ^ * $ Codieren der natürlichen Zahl $ N $ (Ich gehe an, $ 0 \ in \ mathbb {n} $ ) in binärt und arbeitet wie folgt:

• es flippt das letzte Bit von $ x $ . Jetzt $ x $ stellt eine ungerade Anzahl dar, wenn die Eingabenummer $ N $ sogar war.
• es ruft das Oracle für $ B $ mit input $ x $ .
• es akzeptiert IFF, laut Oracle, $ x \ in B $ .

Beachten Sie, dass die Tatsache, dass $ M $ Zugriff auf ein Oracle für $ B $ hat, nicht bedeutet, dass $ M $ dieses Oracle verwenden muss. Folgendes ist auch eine gültige Wahl für $ M $ :

• Suchen Sie das letzte Bit $ y $ der Eingabezeichenfolge $ x $ .
• wenn $ y= 0 $ akzeptieren. Anderweitig ablehnen.