In natürlichen Zahlen reduzierbar?
-
29-09-2020 - |
Frage
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.
Lösung
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
- 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.